Введение в O-нотацию в Go

Зачем мы измеряем алгоритмы

Одна и та же программа работает быстро на новом компьютере и медленно на старом. Поэтому секунды — плохой способ сравнивать два алгоритма: число зависит от машины, а не только от кода.

Вместо этого мы считаем шаги: сколько простых операций выполняет алгоритм. Шаг — это одно небольшое действие, например прочитать значение, сравнить два числа или сложить их.

O-нотация описывает, как растёт число шагов при росте входных данных. Она не говорит «это займёт 3 секунды». Она говорит «если вход удваивается, работа удваивается» — это O(n) — или «если вход удваивается, работа остаётся прежней» — это O(1).

O-нотация смотрит на худший случай: наибольшее число шагов, которое может понадобиться алгоритму для входа размера n.

Подсчёт шагов

Цикл, который проходит по каждому элементу среза, делает по одному проходу на элемент. Для 5 элементов это 5 шагов, для 10 элементов — 10 шагов. Число шагов совпадает с len(nums).

Точное число нас не интересует. Нам важна форма роста: вдвое больше вход — вдвое больше шагов. Такая форма называется линейной и записывается как O(n).

Подсчёт шагов цикла

Функция добавляет внутри цикла счётчик steps++. Срез из 5 элементов требует 5 шагов, срез из 10 элементов — 10 шагов: число шагов следует за размером входных данных.

Напиши на Go функцию, которая суммирует срез значений int и считает с помощью счётчика steps, сколько шагов цикла для этого нужно. Вызови её один раз со срезом из 5 чисел и один раз со срезом из 10 чисел и выведи оба значения счётчика шагов.

> Вывод: программа на Go и захваченный вывод

Prompt

Напиши на Go функцию, которая суммирует срез значений int и считает с помощью счётчика steps, сколько шагов цикла для этого нужно. Вызови её один раз со срезом из 5 чисел и один раз со срезом из 10 чисел и выведи оба значения счётчика шагов.

Вывод: программа на Go и захваченный вывод

package main

import "fmt"

func countSteps(nums []int) int {
  steps := 0
  sum := 0
  for _, n := range nums {
    sum += n
    steps++
  }
  fmt.Println("сумма:", sum)
  return steps
}

func main() {
  small := []int{2, 4, 6, 8, 10}
  big := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

  fmt.Println("шагов для 5 элементов:", countSteps(small))
  fmt.Println("шагов для 10 элементов:", countSteps(big))
}

Удвоение входа удваивает работу

Программа выполняет один и тот же считающий цикл для n = 100, 200 и 400. Каждый раз, когда n удваивается, число шагов тоже удваивается. Это отличительный признак O(n).

Напиши программу на Go, которая для n = 100, 200 и 400 выполняет цикл n раз, подсчитывая шаги, и печатает по одной строке на каждое n с самим n и числом шагов, чтобы я увидел, что удвоение n удваивает число шагов.

> Вывод: программа на Go и захваченный вывод

Prompt

Напиши программу на Go, которая для n = 100, 200 и 400 выполняет цикл n раз, подсчитывая шаги, и печатает по одной строке на каждое n с самим n и числом шагов, чтобы я увидел, что удвоение n удваивает число шагов.

Вывод: программа на Go и захваченный вывод

package main

import "fmt"

func main() {
  for _, n := range []int{100, 200, 400} {
    steps := 0
    for i := 0; i < n; i++ {
      steps++
    }
    fmt.Printf("n = %3d -> %3d шагов\n", n, steps)
  }
}

Классы роста

Большинство алгоритмов попадает в несколько распространённых классов роста, от самого быстрого к самому медленному:

O(1) константное время — работа никогда не растёт.
O(log n) логарифмическое время — удвоение входа добавляет всего один шаг.
O(n) линейное время — работа растёт вместе с входом.
O(n log n) — хороший алгоритм сортировки.
O(n²) квадратичное время — цикл внутри цикла.
O(2ⁿ) экспоненциальное время — работа удваивается с каждым дополнительным элементом.

Для маленьких входных данных разница крошечная. Для больших она решает, ответит программа сразу или не закончит никогда.

Сравнение классов роста

Таблица показывает число шагов для растущего n. При n = 16 значение log n равно всего 4, а 2ⁿ — уже 65536. Чем больше становится n, тем сильнее классы расходятся.

Напиши программу на Go, которая печатает таблицу сравнения классов роста. Для n = 1, 2, 4, 8, 16 выведи по одной строке со значениями: n, log n, n, n log n, n в квадрате и 2 в степени n. Используй math.Log2 и выровняй столбцы с помощью Printf.

> Вывод: программа на Go и захваченный вывод

Prompt

Напиши программу на Go, которая печатает таблицу сравнения классов роста. Для n = 1, 2, 4, 8, 16 выведи по одной строке со значениями: n, log n, n, n log n, n в квадрате и 2 в степени n. Используй math.Log2 и выровняй столбцы с помощью Printf.

Вывод: программа на Go и захваченный вывод

package main

import (
  "fmt"
  "math"
)

func main() {
  fmt.Printf("%5s %7s %5s %9s %6s %8s\n", "n", "log n", "n", "n log n", "n^2", "2^n")
  for _, n := range []int{1, 2, 4, 8, 16} {
    logn := math.Log2(float64(n))
    fmt.Printf("%5d %7.0f %5d %9.0f %6d %8d\n",
      n, logn, n, float64(n)*logn, n*n, int(math.Pow(2, float64(n))))
  }
}

Что O-нотация игнорирует

O-нотация сохраняет только форму роста, а детали отбрасывает. O(2n), O(n + 5) и O(n) — это один и тот же класс: линейный.

Почему? Потому что для больших входных данных постоянный множитель перестаёт иметь значение. Алгоритм, который делает 2 прохода по миллиону элементов, всё равно находится в другом мире, чем тот, который сравнивает каждый элемент с каждым.

Точные правила упрощения — отбросить константы, отбросить меньшие слагаемые — разобраны на отдельной странице далее в этой группе.

Два цикла — это всё равно O(n)

Программа делает два отдельных прохода по срезу: один для суммы, другой для наибольшего значения. Это 2n шагов — 16 для 8 элементов. O-нотация отбрасывает константу 2, поэтому это всё равно O(n).

Напиши программу на Go, которая делает два отдельных прохода по одному и тому же срезу из 8 значений int — один цикл для вычисления суммы, другой для поиска наибольшего значения — и подсчитывает каждый шаг цикла в одном общем счётчике. Выведи сумму, наибольшее значение, количество элементов и общее число шагов.

> Вывод: программа на Go и захваченный вывод

Prompt

Напиши программу на Go, которая делает два отдельных прохода по одному и тому же срезу из 8 значений int — один цикл для вычисления суммы, другой для поиска наибольшего значения — и подсчитывает каждый шаг цикла в одном общем счётчике. Выведи сумму, наибольшее значение, количество элементов и общее число шагов.

Вывод: программа на Go и захваченный вывод

package main

import "fmt"

func main() {
  nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
  steps := 0

  sum := 0
  for _, n := range nums {
    sum += n
    steps++
  }

  max := nums[0]
  for _, n := range nums {
    if n > max {
      max = n
    }
    steps++
  }

  fmt.Println("сумма:", sum)
  fmt.Println("макс:", max)
  fmt.Println("элементов:", len(nums))
  fmt.Println("шагов:", steps)
}