Big O — сложность алгоритмов
Big O — это нотация: способ описать, как растёт объём работы алгоритма, когда данных становится больше.
Два способа обработать десять игроков могут казаться одинаково быстрыми. Но для тысячи игроков одному может понадобиться тысяча проверок, а другому — миллион. Оценка сложности помогает понять эту разницу; точное время выполнения измеряют отдельно.
Начнём с интерактивных примеров: будем менять количество данных и смотреть, сколько шагов делает алгоритм. Затем разберёмся, как по коду самостоятельно оценить его сложность.
Что такое N?
N — это размер данных, с которыми работает алгоритм. Для списка или массива это просто количество элементов:
- В массиве [4, 7, 2, 9, 1] пять чисел, значит, N = 5.
- В списке 100 игроков, значит, N = 100.
- Если мы проверяем пароль символ за символом, N — его длина. Для пароля из восьми символов N = 8.
Буква нужна потому, что один и тот же алгоритм может работать с разным количеством данных. Сегодня в списке 10 записей, а завтра — 1000. Обозначение N подходит для обоих случаев.
N говорит, сколько у нас данных. А число шагов зависит от того, что мы с ними делаем. Прочитать первую запись в списке из 100 игроков можно за одно обращение; проверить каждого игрока — за 100 проверок. В примерах ниже меняйте N и смотрите, как меняется объём работы.
O(1)
Количество операций остаётся постоянным при увеличении числа элементов. Нужная позиция уже известна: алгоритму не приходится обходить остальные данные.
O(1) — прямой доступ по индексу
Псевдокод
O(log N)
Каждый шаг сокращает область поиска примерно вдвое. Удвоение количества элементов добавляет примерно один шаг: это можно увидеть в бинарном поиске и в пути по сбалансированному дереву.
O(log N) — бинарный поиск
Псевдокод
O(N)
Алгоритм проходит по элементам один за другим. Вдвое больше данных — примерно вдвое больше работы. Поиск может завершиться раньше, но в худшем случае потребуется полный проход.
O(N) — ищем слева направо
Псевдокод
O(N log N)
Для каждого из N объектов выполняется логарифмический поиск или вставка. Сравните повторные бинарные поиски с построением таблицы результатов через дерево.
O(N log N) — N объектов, каждый делает log N поиск
Псевдокод
O(N²)
Для каждого элемента выполняется ещё один полный проход: получаются два вложенных цикла. Это видно и в проверках всех пар, и в обходе квадратного поля.
O(N²) — A фиксируется, B проходит весь массив
Псевдокод
O(2ⁿ)
Все наборы снаряжения
Псевдокод
Visit(i):
if i == N: CountVariant(); return
Choose(i, false); Visit(i + 1)
Choose(i, true); Visit(i + 1)O(N!)
Все возможные коды замка
Псевдокод
Visit(depth):
if depth == N: CountVariant(); return
for each unused symbol:
Use(symbol); Visit(depth + 1); Undo(symbol)Как растёт работа
От подсчёта операций к Big O
Прежде чем оценивать алгоритм, ответьте на три вопроса: что в задаче может расти, какую работу мы считаем и для каких входных данных?
- Определите размер задачи. Для списка игроков N — число игроков, для массива — количество элементов. Сначала договоритесь, что именно вы считаете.
- Выберите единицу работы. Например, при поиске числа можно считать сравнения, а при копировании массива — записи элементов.
- Посчитайте, сколько раз выполняется эта работа. Учитывайте и то, что скрыто внутри вызываемых функций. За одной строкой кода может стоять обход или копирование всего массива.
- Оставьте то, что определяет рост. Если получается 3N + 20 операций, записываем O(N). Если N² + N — O(N²). Постоянные множители и слагаемые меньшего порядка убираем из оценки, хотя на практике, особенно при небольших N, они по-прежнему влияют на скорость.
Как распознавать сложность в коде
Эти признаки помогают сориентироваться, но оценку всё равно нужно обосновать подсчётом. Одной вложенности циклов недостаточно. В примерах ниже N — длина массива, а каждый вызов process занимает O(1).
Два вложенных цикла, а сложность — O(N)
for i from 0 to N - 1:
for repeat from 1 to 10:
process(values[i])
Внутренний цикл всегда выполняется десять раз. Всего получается 10N вызовов, то есть O(N), а не O(N²).
Удвоение во внутреннем цикле даёт O(N log N)
for i from 0 to N - 1:
j = 1
while j < N:
process(values[i])
j = j * 2
На каждой итерации внешнего цикла j снова начинается с единицы и удваивается, пока не достигнет N или не превысит его. Это ⌈log₂ N⌉ повторений — логарифм, округлённый вверх. Повторяем такую работу N раз и получаем O(N log N).
Внутренний цикл продолжает с прежнего места
j = 0
for i from 0 to N - 1:
while j < N and values[j] <= values[i]:
j = j + 1
Пусть массив values упорядочен по возрастанию. Здесь j не сбрасывается при переходе к следующему i. За всё выполнение он увеличится не более N раз, а внешний цикл сделает N итераций. Вместе с проверками условий это O(N).
Длина внутреннего прохода меняется: сначала сложите все проходы
for i from 0 to N - 1:
for j from i + 1 to N - 1:
checkPair(values[i], values[j])
Каждую пару разных элементов проверяем ровно один раз. Число проверок равно (N − 1) + (N − 2) + … + 1 = N(N − 1) / 2. Мы избавились от повторных пар и сравнений элемента с самим собой, но порядок роста остался квадратичным: O(N²).
Если в задаче два независимых размера, сохраните оба. Например, проверка каждого из N предметов инвентаря с каждой из M ячеек склада требует O(NM). Заменять эту оценку на O(N²) можно лишь тогда, когда связь между N и M это позволяет.
Сложение и умножение сложностей
Когда этапы выполняются подряд, их стоимость складываем (+). Когда одну работу повторяем внутри другой — перемножаем (×). Разберём оба случая на примере склада, затем упростим итоговую оценку.
Найти предмет
Псевдокод
Сначала складываем стоимость всех этапов, затем упрощаем выражение. O(N + M) нельзя заменить на O(N), если связь между N и M неизвестна. Если объём внутренней работы меняется от шага к шагу, складываем эти объёмы, а не автоматически перемножаем размеры.
Как растёт потребность в памяти
Одна задача — развернуть порядок элементов массива. Оба способа требуют O(N) работы, но используют разное количество памяти. Считаем место сверх исходного массива, включая место под результат. Элементы — числа одинакового размера.
Развернуть на месте
Код этого шага
Что стоит за обозначениями
Big O задаёт верхнюю границу роста. Начиная с некоторого размера задачи, число операций не превышает выбранную функцию, умноженную на постоянный коэффициент. Например, при N ≥ 20 выполняется 3N + 20 ≤ 4N. Поэтому 3N + 20 — это O(N).
Линейный рост можно описать и как O(N²), но такая оценка будет менее точной. Обычно стараются выбрать границу, которая хорошо передаёт характер роста. Обозначение Θ («тета») задаёт точный порядок роста, а Ω («омега») — нижнюю границу. Сами эти символы не означают лучший, средний или худший случай: выбор входных данных и выбор границы — разные вопросы.
Важно, что именно обозначает N. У квадратного поля со стороной N всего N² клеток. Обход всех клеток имеет квадратичную сложность относительно длины стороны, но линейную — относительно числа клеток. Алгоритм остаётся тем же; меняется величина, через которую мы описываем размер задачи.
За одной строкой кода может скрываться много работы. В наших примерах чтение, сравнение и запись значений фиксированного размера занимают постоянное время. С длинными строками и массивами это уже не так: их сравнение или копирование может потребовать целого прохода.
Почему обычно не указывают основание логарифма?
Если на каждом шаге оставлять половину области поиска, получится около log₂ N шагов. Если оставлять десятую часть — около log₁₀ N. Эти величины отличаются лишь постоянным множителем, поэтому обе оценки записывают как O(log N). А вот исключение всего одного кандидата за шаг в худшем случае потребует O(N) шагов.
Амортизированная стоимость
Один push_back. Иногда — целый переезд. Пока есть место, добавление стоит одну запись. Когда блок заполнен, переносим старые элементы в новый.
Высота столбика — число переносов и записей при одном добавлении. Это модель операций, а не замер времени.
Код этого шага
Почему амортизированно O(1)?
При удвоении ёмкости за N добавлений переносов меньше 2N, а записей ровно N. Итого меньше 3N единиц работы: средняя стоимость на всей последовательности ограничена константой. Отдельное добавление при расширении требует O(N).
Удвоение — условие этой модели, а не гарантированный коэффициент роста std::vector. Считаем перенос скалярного элемента и запись за одну операцию; работу аллокатора и деструкторов не моделируем. Это амортизация по последовательности, а не средний случай по случайным входам.