Как растёт стоимость (Big-O)

Что это такое

Big-O описывает форму кривой стоимости, а не показание секундомера. Запись говорит, как меняется число операций с ростом входа, а постоянные множители при этом отбрасываются. Обозначение намеренно грубое: алгоритм, который делает три прохода по данным, и алгоритм с одним проходом оба линейны, потому что разница между ними остаётся неизменной, тогда как разрыв между линейным и квадратичным растёт взрывным образом.

Почему это важно

Замерить каждую конструкцию в масштабе продакшена вы не можете — и не должны этого делать. Записанная скорость роста позволяет отбросить обречённый подход на бумаге, до того как в него вложатся силы. Она же объясняет уже встреченные сюрпризы: ночную задачу, которая при тысяче строк работала нормально, а на миллионе занимает шесть часов, или эндпоинт, чья задержка удвоилась вместе с размером страницы. Привычка спрашивать «как это растёт?» отличает код, протестированный только на игрушечных данных, от кода, который продолжает работать.

Ключевые идеи

Считайте операцию, которая доминирует

Найдите шаг, который повторяется чаще всего с ростом входа, и считайте его. Если цикл выполняет фиксированную работу на элемент, стоимость растёт с числом элементов; если он делает это внутри другого цикла по второй коллекции — с произведением. Добавление постоянного числа других шагов не меняет скорость роста, поэтому запись их игнорирует.

for each row in rows:            # n строк
  total = total + row.amount    # фиксированная работа на строку
# стоимость растёт с n -> линейно

for each row in rows:           # n строк
  for each other in rows:       # по n строк на каждой
    compare(row, other)         # n * n сравнений -> квадрат

Классы роста, которые вы действительно встретите

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

n = 1,000,000
константа        1 шаг
логарифм       ~20 шагов
линейно          1,000,000 шагов
квадрат          1,000,000,000,000 шагов

Лучший, средний и худший случаи

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

Амортизированная стоимость скрывает редкие всплески

Есть операции, которые обычно дешевы, а изредка дороги. Добавление в динамический массив константно, пока массив не полон, а потом копирует всё содержимое; если разложить эту цену на добавления, которые его заполнили, среднее останется константным. Именно это среднее описывает амортизированная стоимость, и о всплеске она не умалчивает. А вот низкой задержки в худшем случае она не обещает — и это важно, когда код выполняется внутри запроса с дедлайном.

Практика

Сначала предскажите, потом измерьте

С помощью вложенного цикла напишите функцию, которая проверяет, есть ли у двух списков общий элемент. Сначала предскажите скорость её роста для списков из 100, 1 000 и 10 000 элементов, а потом замерьте. Перепишите функцию через множество и замерьте снова.

Готово, когда: предсказание совпадает с измеренной формой на всех трёх размерах, а на самом большом из них две реализации расходятся больше чем на порядок.

Найдите скрытый цикл

Возьмите функцию из собственной кодовой базы и посчитайте, сколько раз она проходит по одной и той же коллекции, — включая циклы, спрятанные внутри вызовов библиотек, например фильтрацию внутри отображения.

Готово, когда: вы называете стоимость самого медленного пути через функцию и указываете строку, которая за неё отвечает.

Частые ошибки

Читать O(n) как скорость — запись описывает рост, поэтому линейный алгоритм может обогнать константный на малом входе; исправить: указывайте размер входа, о котором рассуждаете.
Игнорировать постоянный множитель там, где он доминирует — у хеш-таблицы есть затраты на настройку и хеширование, которых нет у сканирования массива из пяти элементов; исправить: отбрасывайте конструкции записью, а остальные замеряйте.
Считать средний случай единственным — патологический вход превращает среднее в худшее; исправить: назовите худший случай и решите, могут ли ваши данные его создать.
Вкладывать сканирование внутрь цикла — квадратичная стоимость невидима в исходнике, но квадратична на данных; исправить: вынесите сканирование в словарь или в множество, которое строится один раз.
Считать только написанные вами строки — сериализация, журналирование и вызовы библиотек внутри цикла тоже входят в стоимость; исправить: считайте всё, что тело цикла действительно выполняет.

Что читать дальше

Структуры данных (01-cs-fundamentals/02-data-structures) — скорости роста на самом деле говорят о структуре, которая хранит ваши данные, поэтому прочитайте его первым.
Сортировка, поиск и обход (01-cs-fundamentals/14-algorithms-big-o/02-sorting-searching-and-traversal) — стандартные алгоритмы вместе с той стоимостью, которую несёт каждый из них.
Внутреннее устройство баз данных (01-cs-fundamentals/04-database-internals) — что значит, когда стоимость определяется диском, а не операциями.