Сложность алгоритма и O-нотация – Учебник

10.1

О чём этот урок

Задача школьная: посчитать сумму всех целых чисел от 1 до N. Способов два, и оба правильные.

Первый – цикл с накопителем: прибавляем числа по одному, пока они не кончатся. Второй – формула, известная задолго до компьютеров: N * (N + 1) // 2. Никакого цикла, одно выражение.

При N = 5 обе программы печатают 15. А теперь подставим миллиард: программа с формулой ответит мгновенно, программа с циклом будет считать десятки секунд. Ответ один и тот же, разница – в способе.

n = 5

total = 0
for i in range(1, n + 1):
    total = total + i
print(total)   # 15

total = n * (n + 1) // 2
print(total)   # 15

Как сравнить два алгоритма, не запуская их, – об этом урок.

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

Что считают вместо секунд

Секунды для сравнения алгоритмов не годятся: одно и то же решение на новом ноутбуке отработает быстрее, чем на школьном, на C – в десятки раз быстрее, чем на Python, а открытый браузер испортит замер сам по себе. Секунды принадлежат машине, а не способу решения.

Поэтому считают элементарные операции.

Элементарная операция – действие, которое выполняется за время, не зависящее от размера данных: сложение, сравнение, присваивание, взятие элемента списка по индексу.

Временная сложность – зависимость количества элементарных операций от размера входных данных N.

Что считать размером входа, зависит от задачи: у списка это его длина, у числа – количество цифр, у строки – длина.

У программы есть и второй ресурс – память.

Пространственная сложность – зависимость объёма дополнительной памяти, которую требует алгоритм, от размера входа N.

Сумма квадратов, собранная в новый список, требует $O(N)$ памяти, а та же сумма циклом с накопителем – $O(1)$: кроме одной переменной ничего не заводится.

Худший случай

У одного алгоритма на входах одного размера число действий может различаться. Линейный поиск идёт по списку с начала и сравнивает элементы с искомым:

искомое лежит первым – хватит одного сравнения, это лучший случай;
искомого в списке нет – придётся проверить все N элементов, это худший случай.

По умолчанию алгоритм оценивают по худшему случаю, потому что только эта оценка даёт гарантию. «Не больше N сравнений» – обещание, которое выполнится на любых данных. Лучший случай не обещает ничего: рассчитывать, что искомое всегда окажется первым, нельзя.

O-нотация

Сравнивать точные выражения вроде $3N^2 + 50N + 1000$ неудобно, да и бессмысленно: у двух аккуратных программистов получатся разные числа. Нужна короткая запись, которая сохраняет главное – характер роста.

O-нотация – запись вида $O(f(N))$: число действий растёт не быстрее $f(N)$ с точностью до постоянного множителя, начиная с некоторого N.

Свернуть выражение помогают три правила.

Правило	Пример
постоянные множители отбрасываем	$3N \to O(N)$
из суммы остаётся старшее слагаемое	$N^2 + 100N + 500 \to O(N^2)$
вложенность умножает, последовательность складывает	цикл в цикле – $N \cdot N$, два цикла подряд – $N + N$

Проверим второе правило на числах. При N = 1000 выражение $N^2 + 100N + 500$ даёт миллион, сто тысяч и пятьсот. Миллион больше остальных вместе взятых, и при дальнейшем росте N разрыв только увеличивается – поэтому хвост отбрасывают.

Основание логарифма тоже не пишут: $\log_2 N$ и $\log_{10} N$ отличаются постоянным множителем, а он по первому правилу не важен. Пишут просто $O(\log N)$.

Классы сложности

На практике встречается немного классов роста.

Запись	Как растёт	Пример
$O(1)$	не растёт вообще	`a[i]`, `len(a)`, формула суммы
$O(\log N)$	каждое удвоение N добавляет один шаг	деление пополам, двоичный поиск (урок 10.5)
$O(N)$	пропорционально N	линейный поиск, `sum()`, `max()`
$O(N \log N)$	чуть быстрее пропорционального	`sorted()` (урок 10.6)
$O(N^2)$	квадратично	двойной перебор пар, простые сортировки (урок 10.3)
$O(2^N)$	взрывообразно	перебор всех наборов N логических переменных

Ту же разницу видно в числах.

N	$\approx \log_2 N$	N	$N^2$
10	3	10	100
100	7	100	10 000
1 000	10	1 000	1 000 000
1 000 000	20	1 000 000	1 000 000 000 000

На маленьких N колонки почти не отличаются, а в последней строке рядом стоят 20 действий и триллион. Слева логарифм вырос всего с 3 до 20 – чтобы прибавить единицу, N должно удвоиться.

Сколько данных успеет каждый класс

Абстракцию удобно перевести в практический вопрос: какого размера данные алгоритм переварит примерно за секунду?

Возьмём оценку порядка $10^7$ простых действий в секунду для Python. Она взята с запасом: замер пустого цикла показал около 40 миллионов шагов в секунду, а перебор пар – около 22 миллионов.

Сложность	Приемлемый N за ~1 секунду
$O(1)$, $O(\log N)$	любой, хоть миллиард
$O(N)$	около 10 000 000
$O(N \log N)$	около 500 000
$O(N^2)$	около 3 000
$O(2^N)$	около 23
$O(N!)$	около 10

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

Коротко

Временная сложность – как число элементарных операций растёт с размером входа N; секунды зависят от машины, а число операций – от алгоритма.
По умолчанию оценивают худший случай: только он даёт гарантию на любых данных.
O-нотация отбрасывает множители и младшие слагаемые: $3N^2 + 50N + 1000$ – это $O(N^2)$.
Вложенность умножает, последовательность складывает; основание логарифма не пишут.
На практике хватает шести классов: $O(1)$, $O(\log N)$, $O(N)$, $O(N \log N)$, $O(N^2)$, $O(2^N)$.
При $10^7$ операций в секунду $O(N^2)$ тянет около 3 000 элементов, а $O(N \log N)$ – около 500 000.

Что нас ждёт в этом блоке

Урок	Тема	О чём
10.1	Сложность и O-нотация	как оценивать алгоритмы без запуска
10.2	Сложность по коду	циклы, скрытые проходы и проверка часами
10.3	Простые сортировки	пузырёк, выбор, вставки
10.4	Быстрая сортировка	опорный элемент и разбиение
10.5	Двоичный поиск	деление отрезка пополам
10.6	Встроенная сортировка	`sorted`, `sort` и `key`