Четыре простых правила
Чтобы превратить вопрос «сколько шагов делает этот код» в класс O-большого, нужны четыре правила:
1. Оставляем худший случай — считаем наибольшее число шагов, которое коду когда-либо может понадобиться.
2. Отбрасываем константы — O(2n) и O(n/2) — это одно и то же O(n).
3. Отбрасываем меньшие слагаемые — O(n + n²) — это O(n²).
4. Разные входные данные — разные буквы — два разных среза дают O(a · b), а не O(n²).
Ниже к каждому правилу есть по одному примеру.
Правило 1: оставляем худший случай
Линейному поиску может повезти: если значение стоит в начале, хватит одного шага. O-большое не учитывает везение и описывает худший случай для среза — значение стоит последним или его вообще нет, и проверяются все n элементов.
Поэтому линейный поиск — это O(n), даже если он часто заканчивается раньше. Худший случай — это обещание, которое алгоритм может выполнить всегда.
Лучший и худший случай поиска
Поиск первого слова занимает 1 шаг. Поиск отсутствующего слова занимает все 5. O-большое оставляет 5: линейный поиск — это O(n).
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func search(words []string, target string) int {
steps := 0
for _, w := range words {
steps++
if w == target {
break
}
}
return steps
}
func main() {
words := []string{"one", "two", "three", "four", "five"}
fmt.Println("лучший случай (\"one\"):", search(words, "one"), "шаг")
fmt.Println("худший случай (\"six\"):", search(words, "six"), "шагов")
}
Правило 2: отбрасываем константы
Цикл, который посещает каждый второй элемент, делает n/2 шагов. Работы вдвое меньше — но форма роста не меняется: удвойте вход, и число шагов удвоится.
O-большое оставляет только форму, поэтому O(n/2), O(n) и O(2n) — это один и тот же класс: линейный.
Вдвое меньше шагов — всё равно O(n)
Цикл шагает через 2 и посещает 4 из 8 элементов. Если срез удвоится, число шагов тоже удвоится — значит, n/2 шагов — это по-прежнему линейный рост, O(n).
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
steps := 0
// Посещаем каждый второй элемент: n/2 шагов.
for i := 0; i < len(nums); i += 2 {
fmt.Print(nums[i], " ")
steps++
}
fmt.Println()
fmt.Println("элементов:", len(nums), "шагов:", steps)
}
Правило 3: отбрасываем меньшие слагаемые
Код часто смешивает части с разной стоимостью: простой цикл (n шагов), за которым идут вложенные циклы (n² шагов). Всего получается n + n².
С ростом n часть n² поглощает всё остальное — при n = 1000 это миллион шагов против тысячи. O-большое оставляет только самое быстрорастущее слагаемое: O(n + n²) превращается в O(n²).
n + n² шагов
Для 6 элементов простой цикл добавляет 6 шагов, а вложенные циклы — 36; всего 42. Квадратичное слагаемое уже преобладает, и его перевес только растёт вместе с n.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{1, 2, 3, 4, 5, 6}
steps := 0
// Один простой цикл: n шагов.
for range nums {
steps++
}
// Цикл внутри цикла: n * n шагов.
for range nums {
for range nums {
steps++
}
}
fmt.Println("n =", len(nums))
fmt.Println("n + n*n =", steps)
}
Правило 4: разные входные данные — разные буквы
Когда вложенные циклы проходят по двум разным входным данным, число шагов равно a · b — произведению двух длин. Назвать это O(n²) было бы неверно: входные данные могут быть очень разного размера.
Честный класс — это O(a · b). Он превращается в O(n²) только в частном случае, когда оба входа — это одно и то же.
Два разных среза
3 цвета, умноженные на 2 животных, дают 6 шагов. Сложность — O(a · b): если срез с животными растёт, а срез с цветами нет, то важно только b.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
colors := []string{"красный", "зелёный", "синий"}
animals := []string{"кот", "собака"}
steps := 0
for range colors {
for range animals {
steps++
}
}
fmt.Println("цвета:", len(colors), "животные:", len(animals))
fmt.Println("шагов:", steps)
}
Границы применимости O-большого
O-большое — намеренно грубый инструмент, и стоит знать, что оно скрывает.
Оно видит только худший случай. Алгоритм со страшным худшим случаем может отлично работать на практике, если этот случай встречается редко. Иногда важен именно средний случай.
Оно не учитывает константы. На бумаге 1000 · n и n — это один класс. На небольших входных данных «более медленный» алгоритм O(n²) с крошечными шагами может обогнать «более быстрый» O(n) с тяжёлыми шагами.
Используйте O-большое, чтобы сравнивать, как алгоритмы масштабируются. А чтобы узнать реальную скорость на реальных данных — измеряйте.