К содержимому

Big O — сложность алгоритмов

Big O — это нотация: способ описать, как растёт объём работы алгоритма, когда данных становится больше.

Два способа обработать десять игроков могут казаться одинаково быстрыми. Но для тысячи игроков одному может понадобиться тысяча проверок, а другому — миллион. Оценка сложности помогает понять эту разницу; точное время выполнения измеряют отдельно.

Начнём с интерактивных примеров: будем менять количество данных и смотреть, сколько шагов делает алгоритм. Затем разберёмся, как по коду самостоятельно оценить его сложность.

Что такое N?

N — это размер данных, с которыми работает алгоритм. Для списка или массива это просто количество элементов:

Буква нужна потому, что один и тот же алгоритм может работать с разным количеством данных. Сегодня в списке 10 записей, а завтра — 1000. Обозначение N подходит для обоих случаев.

N говорит, сколько у нас данных. А число шагов зависит от того, что мы с ними делаем. Прочитать первую запись в списке из 100 игроков можно за одно обращение; проверить каждого игрока — за 100 проверок. В примерах ниже меняйте N и смотрите, как меняется объём работы.

O(1)

Количество операций остаётся постоянным при увеличении числа элементов. Нужная позиция уже известна: алгоритму не приходится обходить остальные данные.

O(1) — прямой доступ по индексу

Шаг 0
Операций: 0
Псевдокод

O(log N)

Каждый шаг сокращает область поиска примерно вдвое. Удвоение количества элементов добавляет примерно один шаг: это можно увидеть в бинарном поиске и в пути по сбалансированному дереву.

O(log N) — бинарный поиск

Шаг 0
Операций: 0
Псевдокод

O(N)

Алгоритм проходит по элементам один за другим. Вдвое больше данных — примерно вдвое больше работы. Поиск может завершиться раньше, но в худшем случае потребуется полный проход.

O(N) — ищем слева направо

Шаг 0
Операций: 0
Псевдокод

O(N log N)

Для каждого из N объектов выполняется логарифмический поиск или вставка. Сравните повторные бинарные поиски с построением таблицы результатов через дерево.

O(N log N) — N объектов, каждый делает log N поиск

Шаг 0
Операций: 0
Псевдокод

O(N²)

Для каждого элемента выполняется ещё один полный проход: получаются два вложенных цикла. Это видно и в проверках всех пар, и в обходе квадратного поля.

O(N²) — A фиксируется, B проходит весь массив

Шаг 0
Операций: 0
Псевдокод

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)

Как растёт работа

232

От подсчёта операций к Big O

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

  1. Определите размер задачи. Для списка игроков N — число игроков, для массива — количество элементов. Сначала договоритесь, что именно вы считаете.
  2. Выберите единицу работы. Например, при поиске числа можно считать сравнения, а при копировании массива — записи элементов.
  3. Посчитайте, сколько раз выполняется эта работа. Учитывайте и то, что скрыто внутри вызываемых функций. За одной строкой кода может стоять обход или копирование всего массива.
  4. Оставьте то, что определяет рост. Если получается 3N + 20 операций, записываем O(N). Если N² + N — O(N²). Постоянные множители и слагаемые меньшего порядка убираем из оценки, хотя на практике, особенно при небольших N, они по-прежнему влияют на скорость.

Как распознавать сложность в коде

O(1) Прямой доступ. Количество данных не влияет на число шагов.
O(log N) Каждый шаг отбрасывает большую часть вариантов: binary search или движение по одной ветке сбалансированного дерева.
O(N) Один полный проход. Обычно i++, foreach, проверка каждого элемента.
O(N log N) N объектов × одна операция O(log N) для каждого: например binary search или путь по сбалансированному дереву.
O(N²) Два вложенных прохода. Каждый с каждым. Таблица N × N.
O(2ⁿ)Два выбора для каждого объекта: перебор всех подмножеств.
O(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. Считаем перенос скалярного элемента и запись за одну операцию; работу аллокатора и деструкторов не моделируем. Это амортизация по последовательности, а не средний случай по случайным входам.