Big O — сложность алгоритмов
Big O описывает, как растёт количество операций алгоритма при увеличении входных данных.
Эту оценку используют, чтобы сравнивать способы решения одной задачи и выбирать алгоритм с учётом объёма данных. Например, обработка десяти игроков может быть быстрой при любом подходе, а для тысячи игроков число проверок уже сильно зависит от выбранного алгоритма. Big O помогает понять, как будет расти эта работа; точное время выполнения измеряют отдельно.
На интерактивных примерах разберём разные типы сложности: от доступа к одному элементу до перебора всех наборов и порядков. Посмотрим, какие операции выполняет алгоритм и почему их количество зависит от размера задачи.
O(1)
Количество операций остаётся постоянным при увеличении числа элементов. Нужная позиция уже известна: алгоритму не приходится обходить остальные данные.
Псевдокод
O(log N)
Каждый шаг сокращает область поиска примерно вдвое. Удвоение количества элементов добавляет примерно один шаг: это можно увидеть в бинарном поиске и в пути по сбалансированному дереву.
Псевдокод
O(N)
Алгоритм проходит по элементам один за другим. Вдвое больше данных — примерно вдвое больше работы. Поиск может завершиться раньше, но в худшем случае потребуется полный проход.
Псевдокод
O(N log N)
Для каждого из N объектов выполняется логарифмический поиск или вставка. Сравните повторные бинарные поиски с построением таблицы результатов через дерево.
Псевдокод
O(N²)
Для каждого элемента выполняется ещё один полный проход: получаются два вложенных цикла. Это видно и в проверках всех пар, и в обходе квадратного поля.
Псевдокод
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)Как распознавать сложность в коде
Как растёт работа
Сложение и умножение сложностей
Когда этапы выполняются подряд, их стоимость складываем (+). Когда одну работу повторяем внутри другой — перемножаем (×). Разберём оба случая на примере склада, затем упростим итоговую оценку.
Псевдокод
Сначала складываем стоимость всех этапов, затем упрощаем выражение. O(N + M) нельзя заменить на O(N), если связь между N и M неизвестна. Если объём внутренней работы меняется от шага к шагу, складываем эти объёмы, а не автоматически перемножаем размеры.
Как растёт потребность в памяти
Одна задача — развернуть порядок элементов массива. Оба способа требуют O(N) работы, но используют разное количество памяти. Считаем место сверх исходного массива, включая место под результат. Элементы — числа одинакового размера.
Развернуть на месте
Код этого шага
Амортизированная стоимость
Один push_back. Иногда — целый переезд. Пока есть место, добавление стоит одну запись. Когда блок заполнен, переносим старые элементы в новый.
Высота столбика — число переносов и записей при одном добавлении. Это модель операций, а не замер времени.
Код этого шага
Почему амортизированно O(1)?
При удвоении ёмкости за N добавлений переносов меньше 2N, а записей ровно N. Итого меньше 3N единиц работы: средняя стоимость на всей последовательности ограничена константой. Отдельное добавление при расширении требует O(N).
Удвоение — условие этой модели, а не гарантированный коэффициент роста std::vector. Считаем перенос скалярного элемента и запись за одну операцию; работу аллокатора и деструкторов не моделируем. Это амортизация по последовательности, а не средний случай по случайным входам.