Насколько быстро? Нотация «O большое»

При миллиарде шагов в секунду метод n² на миллионе значений работает около 17 минут; метод n log n работает 0.02 секунды.

Рост важнее точного счёта

До сих пор мы считали шаги точно: 45 сравнений, 4 обмена, 20 проверок. Точный счёт полезен для маленьких примеров, но зависит от деталей, например останавливается ли сортировка пузырьком раньше или как выбирается опорный элемент. Когда входные данные становятся большими, одно перевешивает всё остальное: как растёт счёт с ростом n. Алгоритм, число шагов которого растёт как n², рано или поздно проиграет алгоритму с ростом n log n, как бы тщательно ни настроили первый.

Нотация «O большое» является краткой записью этого роста. Запись O(n²), читается «O большое от n в квадрате», означает, что при больших n число шагов не больше некоторой константы, умноженной на n². Два правила упрощают работу с ней. Отбрасывай постоянные множители: 3n и n/2 оба O(n). Оставляй только самое быстро растущее слагаемое: n²/2 − n/2, число сравнений сортировки выбором, является O(n²), потому что при больших n почти всё приходится на часть n². Курс MIT 6.006 использует ту же идею, когда сравнивает структуры данных и сортировки по асимптотическому времени работы.

Распространённые скорости роста

• O(1), константа. Работа не зависит от n: прочитать первое значение списка или значение на известной позиции.
• O(log n), логарифм. Каждый шаг делит задачу пополам: двоичный поиск. Миллион значений, около 20 шагов.
• O(n), линейный рост. Каждое значение обрабатывается один раз: линейный поиск, поиск наибольшего значения, сумма списка.
• O(n log n). Сортировка слиянием и быстрая сортировка в среднем. Лучшее, на что способна сортировка сравнениями.
• O(n²), квадратичный рост. Просматривается каждая пара: сортировки пузырьком, выбором и вставками в худшем случае или два цикла, вложенные один в другой.
• O(2ⁿ), экспонента. Работа удваивается с каждым лишним значением: перебор всех подмножеств из n предметов или перекладывание n дисков в Ханойской башне.

Что числа значат в секундах

Пусть компьютер делает миллиард (10⁹) базовых шагов в секунду, это честное круглое число для одного ядра процессора. Вот что каждая скорость роста значит для миллиона значений. O(log n) около 20 шагов, гораздо меньше микросекунды. O(n) миллион шагов, одна миллисекунда. O(n log n) около 20 миллионов шагов, 0.02 секунды. O(n²) 10¹² шагов, тысяча секунд, около 17 минут. O(2ⁿ) не закончить никогда: 2 в степени миллион является числом, в котором больше 300 000 цифр. Поэтому выбор правильного алгоритма обычно важнее покупки более быстрого компьютера. Машина в десять раз быстрее превращает 17 минут в 1.7 минуты; переход от O(n²) к O(n log n) превращает их в пятидесятую долю секунды.

Как прочитать «O большое» по коду

Скорость роста часто видна прямо по форме кода. Один цикл по списку даёт O(n). Два цикла, один внутри другого, оба по списку, дают O(n²): на каждый из n кругов внешнего цикла внутренний делает до n кругов. Цикл, который каждый раз делит число пополам, например while (n > 1) n = Math.floor(n / 2), даёт O(log n): от 1000 он выполняется 9 раз, от миллиона 19 раз. Шаги, идущие один за другим, складываются, и побеждает большее слагаемое: цикл O(n), за которым идёт цикл O(n²), в целом даёт O(n²).

// O(n): один проход
let total = 0;
for (const x of list) total += x;

// O(n²): каждая пара
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): деление пополам
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

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

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