Четыре простых правила
Чтобы превратить «сколько шагов делает этот код» в класс Big O, нужны четыре правила:
1. Оставляем худший случай — считаем наибольшее число шагов, которое коду вообще может понадобиться.
2. Отбрасываем константы — O(2n) и O(n/2) — это оба O(n).
3. Отбрасываем меньшие слагаемые — O(n + n²) — это O(n²).
4. Разные входные данные получают разные буквы — два разных массива дают O(a · b), а не O(n²).
Ниже для каждого правила есть один пример.
Правило 1: оставляем худший случай
Линейному поиску может повезти: если значение стоит в начале, хватит одного шага. Big O не учитывает везение и описывает худший случай для массива — значение стоит последним или отсутствует, и проверяются все n элементов.
Поэтому линейный поиск — это O(n), хотя он часто заканчивается раньше. Худший случай — это обещание, которое алгоритм может выполнить всегда.
Лучший и худший случай поиска
Поиск первого слова занимает 1 шаг. Поиск отсутствующего слова занимает все 5. Big O оставляет 5: линейный поиск — это O(n).
Вывод: программа на TypeScript и захваченный вывод
function search(words: string[], target: string): number {
let steps = 0
for (const word of words) {
steps++
if (word === target) {
break
}
}
return steps
}
const words = ["one", "two", "three", "four", "five"]
console.log('лучший случай ("one"):', search(words, "one"), "шаг")
console.log('худший случай ("six"):', search(words, "six"), "шагов")
Правило 2: отбрасываем константы
Цикл, который посещает каждый второй элемент, делает n/2 шагов. Работы вдвое меньше — но форма роста не меняется: удвойте вход, и шагов станет вдвое больше.
Big O оставляет только форму, поэтому O(n/2), O(n) и O(2n) — это один и тот же класс: линейный.
Вдвое меньше шагов — всё равно O(n)
Цикл шагает через 2 и посещает 4 из 8 элементов. Если массив станет вдвое больше, шагов тоже станет вдвое больше — значит, n/2 шагов — это по-прежнему линейный рост, O(n).
Вывод: программа на TypeScript и захваченный вывод
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
const visited: number[] = []
let steps = 0
// Посещаем каждый второй элемент: n/2 шагов.
for (let i = 0; i < nums.length; i += 2) {
visited.push(nums[i])
steps++
}
console.log(visited.join(" "))
console.log("элементы:", nums.length, "шаги:", steps)
Правило 3: отбрасываем меньшие слагаемые
В коде часто смешиваются части с разной стоимостью: простой цикл (n шагов), а за ним вложенные циклы (n² шагов). Всего получается n + n².
С ростом n часть n² поглощает всё остальное — при n = 1000 это миллион шагов против тысячи. Big O оставляет только самое быстрорастущее слагаемое: O(n + n²) превращается в O(n²).
n + n² шагов
Для 6 элементов простой цикл добавляет 6 шагов, а вложенные циклы — 36, итого 42. Квадратичное слагаемое уже доминирует, и его перевес только растёт вместе с n.
Вывод: программа на TypeScript и захваченный вывод
const nums = [1, 2, 3, 4, 5, 6]
const n = nums.length
let steps = 0
// Один простой цикл: n шагов.
for (let i = 0; i < n; i++) {
steps++
}
// Цикл внутри цикла: n * n шагов.
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
steps++
}
}
console.log("n =", n)
console.log("n + n*n =", steps)
Правило 4: разные входные данные — разные буквы
Когда вложенные циклы проходят по двум разным входным данным, число шагов равно a · b — произведению двух длин. Назвать это O(n²) было бы неверно: размеры входных данных могут сильно отличаться.
Честный класс — это O(a · b). Он становится O(n²) только в особом случае, когда оба входа — это одно и то же.
Два разных массива
3 цвета умножить на 2 животных — это 6 шагов. Сложность равна O(a · b): если массив животных растёт, а массив цветов нет, то значение имеет только b.
Вывод: программа на TypeScript и захваченный вывод
const colors = ["красный", "зелёный", "синий"]
const animals = ["кошка", "собака"]
let steps = 0
for (let i = 0; i < colors.length; i++) {
for (let j = 0; j < animals.length; j++) {
steps++
}
}
console.log("цвета:", colors.length, "животные:", animals.length)
console.log("шаги:", steps)
Границы применимости Big O
Big O намеренно является грубым инструментом, и полезно знать, что он скрывает.
Он видит только худший случай. Алгоритм со страшным худшим случаем может быть отличным на практике, если этот случай редок. Иногда важен именно средний случай.
Он не учитывает константы. На бумаге 1000 · n и n — это один класс. На небольших входных данных «медленный» алгоритм O(n²) с крошечными шагами может обогнать «быстрый» O(n) с тяжёлыми шагами.
Используйте Big O, чтобы сравнивать, как алгоритмы масштабируются. А для реальной скорости на реальных данных — измеряйте.