O-большое

Ниже шесть фрагментов кода, каждый на Python и на Go. Угадайте, как растёт время их работы, когда растёт n, — а потом посмотрите, что показал замер на сервере этого сайта. Подсказка: в двух фрагментах ответ зависит от языка. Переключите язык и проверьте, какие.

Самое коварное — третий и четвёртый фрагменты. Код одинаковый, а рост разный: строку, которую дописывают по символу, Python тайком удлиняет на месте, а Go каждый раз копирует целиком; список Python, у которого снимают первый элемент, сдвигает весь хвост, а срез Go лишь сдвигает начало окна. По тексту программы этого не увидеть — нужно знать, что стоит за каждой операцией. Об этом вся статья: как описать рост одной формулой и как не ошибиться, когда её выводишь.

Идея

Мерить алгоритмы в секундах неудобно: секунды зависят от машины, языка и данных. Зато почти всегда можно сказать, как растёт число шагов, когда растёт размер входа n, — линейно, как квадрат, как логарифм. Запись f(n) = O(g(n)) означает: начиная с некоторого n, f растёт не быстрее g, с точностью до постоянного множителя.

Два параметра в определении — две уступки. Множитель c разрешает не обращать внимания на постоянную цену шага: на быстрой машине она меньше, на медленной больше, а рост тот же. Номер n₀ разрешает не смотреть на маленькие входы: важно, что происходит, когда данных становится много. Попробуйте сами подобрать c и n₀:

Для 3n² + 50n + 400 подходит, например, c = 4 и n₀ = 58: при n ≥ 58 младшие слагаемые 50n + 400 не больше n², и вся сумма не больше 4n². Отсюда правило: у многочлена важна только старшая степень. Третья пара учит другому: n log n + 1000n = O(n log n), но множитель нужен огромный — младшее слагаемое 1000n догоняет n log₂ n только при n = 2¹⁰⁰⁰. Формально константа не важна, на практике она решает всё. А четвёртая пара — пример того, как определение отказывает: n² не равно O(n log n). Отношение n²/(n log n) = n/log n растёт без предела, и для любого c найдётся n, где n² больше c·n log n.

O, Ω и Θ

O — только верхняя граница. Формально верно, что 5n = O(n²): линейная функция растёт не быстрее квадратичной. Чтобы сказать точнее, нужны ещё два значка:

• Ω — нижняя граница: f = Ω(g), если f(n) ≥ c·g(n) при некотором c > 0 и всех больших n. Любая сортировка сравнениями делает Ω(n log n) сравнений в худшем случае — это доказано в статье о нижней границе.
• Θ — точная оценка: f = Θ(g), если одновременно f = O(g) и f = Ω(g). Сортировка слиянием работает за Θ(n log n) на любом входе.

В разговоре и в документации пишут O, а имеют в виду почти всегда Θ: «поиск в словаре — O(1)» значит «не дольше константы и не быстрее». Это не страшно, пока помнишь разницу. И ещё одна тонкость: O ничего не говорит о том, какой это случай. У быстрой сортировки худший случай Θ(n²), а среднее Θ(n log n); у динамического массива один append стоит Θ(n), а в среднем по любой последовательности — O(1) амортизированно. Говоря о сложности, всегда стоит уточнять: худший случай, средний или амортизированный.

Как оценивать код

Для большинства программ хватает нескольких правил:

• Последовательные части складываются, и остаётся большее: O(n) + O(n log n) = O(n log n). Сортировка и потом линейный проход — это O(n log n).
• Вложенные циклы перемножаются, если число шагов внутреннего не зависит от внешнего: два цикла по n — O(n²).
• Если зависит — считайте сумму. Цикл for j in range(i) внутри цикла по i делает 0 + 1 + … + (n − 1) = n(n − 1)/2 шагов: тоже квадрат. А цикл с шагом i из пятого фрагмента делает n/1 + n/2 + … + n/n ≈ n ln n: два вложенных цикла, а не квадрат.
• Цикл, который делит размер пополам, делает log₂ n шагов. Основание логарифма в O не пишут: log₂ n и log₁₀ n отличаются в постоянное число раз, log₂ 10 ≈ 3,32.
• Рекурсия даёт уравнение. Сортировка слиянием: T(n) = 2T(n/2) + n, отсюда n log n; такие уравнения решает основная теорема. Наивные числа Фибоначчи: T(n) = T(n − 1) + T(n − 2) + 1 — растёт как сами числа Фибоначчи, то есть как 1,618ⁿ.
• Библиотечный вызов — не один шаг. x in list, list.pop(0), list.insert(0, x), срез a[1:] в Python, slices.Contains и s += "x" в Go — все O(n). Сложность каждой операции стоит знать для своего языка; викторина выше — про это.

Если вывести формулу трудно, есть простая проверка — тест удвоения. Запустите программу на n и на 2n и посмотрите, во сколько раз выросла работа. Если она растёт как n^k, отношение будет 2^k, и k = log₂ отношения. Надёжнее всего считать не время, а шаги:

Код

Треугольный цикл даёт ровно 2,00, тройной — 2,99. Деление пополам — 0,07: удвоение n добавляет к логарифму всего один шаг. А вот n log n показывает 1,08 — от линейного роста его на удвоении почти не отличить; разница проявляется, только если растить n на много порядков. Для экспоненты удвоение бессмысленно, и смотрят на шаг n → n + 1: число вызовов наивного Фибоначчи растёт ровно в 1,618 раза — в золотое сечение.

Со временем вместо шагов всё то же самое, только с шумом. Вот замер всех шести фрагментов викторины: на логарифмических осях наклон линии — показатель роста.

Чего O не говорит

Асимптотика сравнивает алгоритмы на очень больших входах и молчит обо всём остальном. Вот что она прячет:

• Константу. 1000·n log₂ n больше, чем n², при любом n примерно до четырнадцати тысяч: алгоритм получше асимптотически проигрывает, пока данных мало. Поэтому библиотечные сортировки добивают маленькие куски вставками: на десятке элементов квадратичный алгоритм с крошечной константой быстрее.
• Память. Поиск в хеш-таблице — O(1), но на миллионе ключей он в разы дороже, чем на тысяче: большая таблица не помещается в кэш процессора. Это видно в викторине на поиске в множестве и в статье о хеш-таблице.
• Какие бывают входы. Худший случай может не встречаться никогда, а может приходить от противника — как убийца быстрой сортировки.
• Сколько это в секундах. Чтобы перевести шаги в секунды, нужна скорость языка и машины — об этом статья «Сколько операций в секунду».

Сама оценка ничего не стоит: её делают в уме, по тексту программы. И почти всегда она отвечает на главный вопрос — растёт ли работа так, что при десятикратном росте данных программа замедлится в десять раз, в сто или в тысячу.

История

Значок O придумали математики задолго до компьютеров. Пауль Бахман ввёл его в 1894 году в книге об аналитической теории чисел, чтобы писать о порядке величины ошибки, а Эдмунд Ландау в 1909 году сделал его привычным — поэтому O, o и родственные значки называют символами Ландау. Применять их к числу шагов программ стали в 1960-е: в 1965 году Юрис Хартманис и Ричард Стернз в статье «О вычислительной сложности алгоритмов» предложили мерить задачи тем, как время работы растёт с длиной входа, и в 1993 году получили за это премию Тьюринга. Ω и Θ в нынешнем смысле закрепил Дональд Кнут в 1976 году в заметке «Big Omicron and big Omega and big Theta»: он предложил, чтобы все писали их одинаково.

Задача

Пятый фрагмент викторины, но с n до 10¹¹. Ответ — сколько раз выполнится внутренняя строка; сначала оцените, сколько это шагов, и станет ясно, что программу из условия запускать бесполезно.