Сложность алгоритмов: O-нотация и классы скорости роста

Программа, которая мгновенно обрабатывает сто строк, на миллионе виснет намертво. Погони за железом здесь обычно нет: умирает не машина, а алгоритм, который делает слишком много работы. Умение заранее оценить, сколько шагов сделает алгоритм на входе размера $n$, отделяет инженера от человека, копирующего код со Stack Overflow. Оценка эта записывается специальным языком — O-нотацией, и после этого урока вы будете читать записи вроде $O(n\log n)$ как открытую книгу.

Время работы и размер входа#

Секунды — плохая мера работы алгоритма: они зависят от процессора, языка и настроения компилятора. Вместо этого считают базовые операции — сравнения, присваивания, обращения к памяти — и смотрят, как их число растёт вместе с размером входа $n$: длиной массива, числом вершин графа, количеством строк. Обычно интересуются худшим случаем: гарантия «не дольше, чем столько-то» полезнее средних обещаний, когда на кону отзывчивость системы. Функцию $T(n)$ — число операций в худшем случае — и описывает O-нотация.

Читаем определение по-человечески: $T(n)$ растёт не быстрее, чем $g(n)$, если константный множитель и участок малых $n$ не считать. Запись $3n^2+100n+7=O(n^2)$ верна: при $n\ge 100$ сумма не превышает $4n^2$, константа $C=4$ найдена. Рядом живут два соседа: $\Omega$ — оценка снизу («растёт не медленнее»), $\Theta$ — точная зажимающая оценка с обеих сторон. На практике чаще всего пишут $O$, имея в виду разумную верхнюю границу порядка роста.

Правила работы с O-нотацией#

Четыре правила снимают почти все вопросы упрощения. Первое — константы не важны: $5n=O(n)$, потому что множитель зажат в $C$ из определения. Второе — младшие слагаемые отбрасываются: при больших $n$ член высшего порядка съедает все остальные, что и показал график выше. Третье — сумма порядков равна максимуму: $O(n^2)+O(n)=O(n^2)$, медленная часть прячется за быстрой. Четвёртое — основание логарифма не важно: ${\log }_{2}n={\log }_{2}e\cdot \ln n$, а изменение основания — тоже константный множитель, поэтому пишут просто $O(\log n)$. Произведения же остаются как есть: $O(n)\cdot O(n)=O(n^2)$ — вложенные циклы умножают работы.

Таблица стоит любого десятка определений. При $n=1000$ квадратичный алгоритм делает миллион операций — компьютеру смешно. При $n=10^6$ это уже $10^{12}$ операций: на машине со $10^9$ операций в секунду — семнадцать минут против долей секунды у линейного прохода и около $2\cdot 10^7$ операций у $O(n\log n)$. Рост порядка — это не «чуть медленнее», это смена категории: от мгновения к минутам, от минут к годам.

Оговорка о честности: сложность бывает не только худшей. Быстрая сортировка в среднем делает $O(n\log n)$ операций, но на неудачных опорных элементах деградирует до $O(n^2)$ — поэтому в библиотеках её страхуют переключением на другой алгоритм или случайным выбором опоры. Когда в задаче не сказано, о каком случае речь, спрашивайте сами: худший даёт гарантию, средний — ожидание, и это разные обещания.

Учимся считать: разбор типовых алгоритмов#

Оценка сложности — это подсчёт операций, а не гадание. Бинарный поиск в отсортированном массиве: на каждом шаге половина выбрасывается, размер задачи идёт $n\to n/2\to n/4\to \dots$ — вопрос «за сколько шагов останется один элемент?» равен вопросу «сколько раз $n$ делится на 2», ответ ${\log }_{2}n$. Для миллиона элементов — около $20$ шагов: $2^{20}=1048576>10^6$. Логарифмическая сложность — фирменный знак «делим задачу пополам»; тот же счёт ведёт к глубине сбалансированных деревьев в структурах данных.

Вложенные циклы умножают. Внешний цикл по $i$ от 1 до $n$, внутренний — по $j$ от 1 до $i$: на $i$-м витке внутренний делает $i$ операций, всего $1+2+\cdots +n=\frac{n(n+1)}{2}\approx \frac{n^2}{2}$. Половинка — константа, а сумма старших членов — снова $n^2$: ответ $O(n^2)$. Сортировка слиянием делит массив пополам и сливает: рекуррента $T(n)=2T(n/2)+n$ разворачивается в ${\log }_{2}n$ уровней по $n$ операций, итого $O(n\log n)$ — развёртка показана в уроке о рекуррентных соотношениях. А перебор всех маршрутов коммивояжёра делает $\frac{(n-1)!}{2}$ вариантов — факториал, против которого бессильна любая техника; прогресс здесь возможен только сменой постановки задачи.

1. 1
   Внешний цикл выполняется $n$ раз; на витке с номером $i$ внутренний цикл делает $i$ операций.
2. 2
   Суммируем: $T(n)=1+2+3+\cdots +n$.
3. 3
   Арифметическая прогрессия: $T(n)=\frac{n(n+1)}{2}=\frac{n^2+n}{2}$.
4. 4
   Упрощаем по правилам O-нотации: $\frac{1}{2}$ — константа, слагаемое $n$ — младший порядок. Остаётся $n^2$.
5. 5
   Ответ: $O(n^2)$. Контрольная проверка: при $n=100$ получаем $\frac{100\cdot 101}{2}=5050$ операций — между $n$ и $n^2$, ближе к квадрату.

P, NP и честная граница мечты#

Классы сложности делят задачи не по алгоритмам, а по самим задачам. P — задачи, решаемые за полиномиальное время, вроде сортировки ($O(n\log n)$) или кратчайших путей у Дейкстры из соответствующего урока. NP — задачи, чей ответ можно быстро проверить: показать готовый маршрут коммивояжёра длиной меньше K — минутное дело, а найти такой — неизвестно как. Вопрос «совпадают ли P и NP» — открытая проблема с миллионным призом; практический итог знают все: для NP-трудных задач заменяют точные алгоритмы приближенными и эвристиками.

Куда двигаться дальше? Сложность неразрывна с рекуррентами: любое время рекурсии — рекуррентное соотношение, и уметь его разворачивать — половина дела. Другая половина — практика: считайте операции в собственном коде, найдите двойной цикл и спросите себя, не обойтись одним проходом. Заодно посмотрите потоки в сетях — там алгоритм Форда-Фалкерсона оценивается числом итераций, и это живой пример того, как анализ сложности выбирает между вариантами реализации.

Финальная проверка наблюдательности: в таблице выше $O(n!)$ для $n=100$ записан как $9,3\cdot 10^{157}$ — посчитано через формулу Стирлинга, а само число шагов алгоритма коммивояжёра, $(n-1)!/2$, для $n=15$ уже превысит сорок миллиардов. Числа такого масштаба — лучшая мотивация выучить факториал не как значок калькулятора, а как реальную категорию медлительности. Ну а считать перестановки и сочетания быстро — отдельный навык, его качает тренажёр по комбинаторике.