Big O нотация простыми словами: как оценивать сложность алгоритмов

«O(n log n) в среднем случае» — фраза, которую многие разработчики повторяют на собеседованиях, толком не понимая, что она означает на практике. Big O превращается в набор заученных ярлыков: «список — это O(n)», «хеш-таблица — O(1)», «сортировка — O(n log n)». Ярлыки работают, пока не встречается ситуация, где интуиция подводит: код с «плохой» асимптотикой оказывается быстрее кода с «хорошей». Разберёмся, что Big O на самом деле измеряет, а что — принципиально нет.

Big O — это про рост, а не про секунды

Главная путаница начинается с того, что Big O воспринимают как оценку скорости. На самом деле это оценка того, как стоимость операции (по времени или по памяти) растёт при увеличении объёма входных данных — и ничего больше. Она намеренно игнорирует константы и «мелкие» слагаемые, потому что интересуется поведением на больших n, а не конкретной цифрой в миллисекундах на конкретном железе.

Именно поэтому алгоритм с O(n) может на практике оказаться медленнее алгоритма с O(n²) — если у первого огромная константа (например, тяжёлая операция внутри каждой итерации), а у второго n маленькое и константа крошечная. Big O ничего не говорит про абсолютное время выполнения при конкретном n — она говорит, что произойдёт с этим временем, если n вырастет в 10 или 100 раз.

Основные классы сложности, которые встречаются в реальном коде

Полезно держать в голове не формальные определения, а интуицию за каждым классом:

• O(1) — константное время. Доступ к элементу массива по индексу или чтение по ключу из хеш-таблицы: сколько бы данных ни было, операция стоит одинаково.
• O(log n) — логарифмическое время. Бинарный поиск в отсортированном массиве: каждый шаг отбрасывает половину оставшихся вариантов, поэтому даже миллиард элементов «схлопывается» до примерно тридцати шагов.
• O(n) — линейное время. Один проход по списку: удвоили данные — удвоилось время.
• O(n log n) — типичная сложность хороших алгоритмов сортировки (merge sort, quicksort в среднем случае): чуть хуже линейного, но на порядки лучше квадратичного на больших объёмах.
• O(n²) — квадратичное время. Часто возникает из вложенных циклов по одним и тем же данным, например наивное сравнение каждого элемента с каждым.

Разница между этими классами не абстрактная: при n = 1 000 000 линейный алгоритм делает миллион операций, а квадратичный — триллион. На таком масштабе разница в асимптотике перестаёт быть теоретической и становится разницей между «работает за секунду» и «не дождёшься».

Худший случай — не единственный случай

Один из самых частых источников ошибок — путать сложность в худшем случае со сложностью в среднем или типичном случае. Quicksort в average case ведёт себя как O(n log n), но в худшем случае (например, на уже отсортированных данных при неудачном выборе опорного элемента) деградирует до O(n²). Хеш-таблица в среднем даёт O(1) на доступ, но при массовых коллизиях в худшем случае может выродиться в O(n).

Когда в задаче или в код-ревью говорят просто «O(n)» без уточнения, о каком случае речь, это часто скрывает важную деталь: для одних данных алгоритм действительно быстрый, а для других — нет. В продакшене входные данные редко бывают «случайными» в математическом смысле, поэтому стоит явно спрашивать: сложность для каких данных мы вообще обсуждаем.

Когда Big O не должна быть единственным аргументом

Big O полезна для сравнения того, как алгоритмы будут вести себя при росте данных, но она ничего не говорит про то, что происходит при конкретных, часто небольших n, с которыми реально работает код. Массив из десяти элементов почти всегда быстрее обработать линейным поиском, чем городить бинарный поиск с предварительной сортировкой, — накладные расходы на асимптотически «лучший» алгоритм на таком масштабе не окупаются.

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

Big O описывает, как алгоритм будет вести себя, когда данных станет намного больше — а не то, насколько он быстр прямо сейчас, на тех данных, что у вас есть сегодня.

Итог

Big O — удобный язык для разговора о масштабируемости алгоритма, но не замена измерениям и профилированию. Она помогает предсказать, что случится с производительностью, если объём данных вырастет на порядок, и в этом её главная ценность. Полезнее воспринимать её не как оценку конкретной программы «в вакууме», а как инструмент для сравнения роста стоимости операции — и всегда уточнять, о каком случае (лучшем, среднем или худшем) идёт речь, прежде чем делать выводы.