Big O Notation

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

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

Разница видна на числах. При n = 1 000 линейный алгоритм O(n) сделает 1 000 шагов, а квадратичный O(n²) - 1 000 000 шагов. При n = 1 000 000 разрыв станет триллион против миллиона - вот что на самом деле стоит за буквой «O».

У большинства классов сложности есть узнаваемый признак прямо в структуре кода - не нужно ничего пересчитывать, чтобы прикинуть класс на глаз.

• Один цикл без вложенности по всем n элементам - O(n).
• Цикл внутри цикла, оба по n элементам - O(n²).
• Размер входа делится пополам на каждом шаге (бинарный поиск, разбиение в Quick Sort) - O(log n).
• Внутри одного цикла вызывается ещё одна O(n)-операция (например .includes() внутри for) - спрятанный O(n²), частая ошибка.
• Постоянное число действий, не зависящее от n (доступ по индексу массива) - O(1).

Постоянные множители не учитываются: цикл, который делает 5 операций на каждый элемент, всё равно O(n), а не O(5n) - Big O описывает форму роста, а не точное число шагов.

У одного и того же алгоритма может быть несколько разных чисел Big O - в зависимости от того, какие данные ему достались. Линейный поиск находит элемент за 1 шаг, если он первый (лучший случай, O(1)), в среднем проверяет половину массива на случайных данных (средний случай, O(n)), и проверяет весь массив, если элемента нет вообще (худший случай, O(n)).

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

Дальше в этом разделе - подробный разбор каждого класса: график роста, разбор кода и примеры из уже реализованных сортировок.

Восемь классов выше покрывают почти весь код, который реально пишут в индустрии, но существуют и более редкие классы. Они не получили в этом разделе отдельных страниц - каждый либо частный случай уже разобранных восьми, либо встречается настолько редко, что для него не нужна отдельная карточка.

• O(√n) - корневая, растёт быстрее логарифма, но заметно медленнее линейной. Пример: проверка числа на простоту перебором делителей только до квадратного корня из него - для миллиона это тысяча проверок вместо миллиона.
• O(log log n) - ещё медленнее логарифма. Пример: дерево ван Эмде Боаса для операций «предшественник» и «преемник», интерполяционный поиск в среднем случае на равномерно распределённых отсортированных данных.
• Смешанные классы вроде O(n log² n) - возникают, когда одна структура данных с логарифмической стоимостью операции вложена в цикл на n элементов. Пример: персистентное дерево отрезков, где каждый из n запросов сам стоит O(log² n).
• O(nᵏ) при k больше трёх - обобщённая полиномиальная сложность, о которой уже говорилось в материале про O(n³). Пример: перебор всех четвёрок элементов массива, чтобы проверить, образуют ли какие-то из них прямоугольник, - O(n⁴).
• O(nⁿ) - гипотетический класс хуже факториала: растёт даже быстрее n!, потому что на каждом из n шагов выбор идёт заново из всех n вариантов, а не из уменьшающегося набора, как при переборе перестановок. Почти не встречается в реальных алгоритмах - обычно это признак кода, который стоит переписать.

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