Зачем измерять алгоритмы
Одна и та же программа работает быстро на новом компьютере и медленно на старом. Поэтому секунды — плохой способ сравнивать два алгоритма: число зависит от машины, а не только от кода.
Вместо этого мы считаем шаги: сколько простых операций выполняет алгоритм. Шаг — это одно небольшое действие, например чтение значения, сравнение двух чисел или их сложение.
Нотация Big O описывает, как растёт число шагов при росте входных данных. Она не говорит «это занимает 3 секунды». Она говорит «если вход удваивается, работа удваивается» — это O(n) — или «если вход удваивается, работа остаётся той же» — это O(1).
Big O смотрит на худший случай: на наибольшее число шагов, которое алгоритму может понадобиться для входа размера n.
Подсчёт шагов
Цикл, который обходит каждый элемент массива, делает один проход на элемент. Для 5 элементов это 5 шагов, для 10 элементов — 10 шагов. Число шагов совпадает с count($nums).
Точное число нас не интересует. Нас интересует форма роста: вдвое больше входных данных — вдвое больше шагов. Такую форму называют линейной и записывают как O(n).
Считаем шаги цикла
Функция добавляет внутрь цикла счётчик $steps++. Массив из 5 элементов требует 5 шагов, массив из 10 элементов — 10 шагов: число шагов следует за размером входных данных.
Вывод: PHP-скрипт
<?php
function countSteps(array $nums): int {
$steps = 0;
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
$steps++;
}
echo "сумма: $sum\n";
return $steps;
}
$small = [2, 4, 6, 8, 10];
$big = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
printf("шагов для 5 элементов: %d\n", countSteps($small));
printf("шагов для 10 элементов: %d\n", countSteps($big));
Удвоение входа удваивает работу
Программа выполняет один и тот же считающий цикл для n = 100, 200 и 400. Каждый раз, когда n удваивается, число шагов тоже удваивается. Это отличительный признак O(n).
Вывод: PHP-скрипт
<?php
foreach ([100, 200, 400] as $n) {
$steps = 0;
for ($i = 0; $i < $n; $i++) {
$steps++;
}
printf("n = %3d -> %3d шагов\n", $n, $steps);
}
Классы роста
Большинство алгоритмов попадает в несколько распространённых классов роста, от самого быстрого к самому медленному:
O(1) константный — работа не растёт вовсе.O(log n) логарифмический — удвоение входа добавляет всего один шаг.O(n) линейный — работа растёт вместе с входными данными.O(n log n) — хороший алгоритм сортировки.O(n²) квадратичный — цикл внутри цикла.O(2ⁿ) экспоненциальный — работа удваивается с каждым дополнительным элементом.
На малых входных данных разница ничтожна. На больших она решает, ответит программа сразу или не завершится никогда.
Сравниваем классы роста
Таблица показывает число шагов для растущего n. При n = 16 величина log n равна всего 4, тогда как 2ⁿ — уже 65536. Чем больше n, тем сильнее классы расходятся.
Вывод: PHP-скрипт
<?php
printf("%5s %7s %5s %9s %6s %8s\n", "n", "log n", "n", "n log n", "n^2", "2^n");
foreach ([1, 2, 4, 8, 16] as $n) {
$logn = log($n, 2);
printf("%5d %7.0f %5d %9.0f %6d %8d\n", $n, $logn, $n, $n * $logn, $n * $n, 2 ** $n);
}
Что Big O игнорирует
Big O сохраняет только форму роста и отбрасывает подробности. O(2n), O(n + 5) и O(n) — это один и тот же класс: линейный.
Почему? Потому что на больших входных данных постоянный множитель перестаёт иметь значение. Алгоритм, который делает 2 прохода по миллиону элементов, всё равно находится в совершенно другом мире, чем тот, который сравнивает каждый элемент с каждым.
Точные правила упрощения — отбросить константы, отбросить меньшие слагаемые — рассматриваются на отдельной странице далее в этой группе.
Два цикла — это всё равно O(n)
Программа делает два отдельных прохода по массиву: один для суммы, другой для наибольшего значения. Это 2n шагов — 16 для 8 элементов. Big O отбрасывает константу 2, поэтому это по-прежнему O(n).
Вывод: PHP-скрипт
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$steps = 0;
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
$steps++;
}
$max = $nums[0];
foreach ($nums as $n) {
if ($n > $max) {
$max = $n;
}
$steps++;
}
echo "сумма: $sum\n";
echo "максимум: $max\n";
echo "элементов: ", count($nums), "\n";
echo "шагов: $steps\n";