Когда объём работы удваивается
O(2ⁿ) означает экспоненциальное время: один дополнительный элемент входных данных удваивает объём работы. Это тот класс роста, в котором алгоритмы перестают быть пригодными — и не для огромных входных данных, а уже для средних.
Экспоненциальная работа обычно возникает из ветвящейся рекурсии: функция вызывает себя дважды, и каждый из этих вызовов снова вызывает себя дважды. Вызовы образуют дерево, которое удваивается на каждом уровне.
Рекурсивные числа Фибоначчи
Последовательность Фибоначчи начинается с 0, 1, и каждое следующее число равно сумме двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, …
Это определение напрямую переводится в рекурсивную функцию: fib($n) возвращает fib($n - 1) + fib($n - 2). Коротко и правильно — и экспоненциально, потому что каждый вызов порождает ещё два, а одни и те же значения вычисляются снова и снова. Только fib(2) внутри более крупного вызова пересчитывается тысячи раз.
Числа Фибоначчи через рекурсию
Счётчик, переданный по ссылке, считает каждый вызов. Вычисление fib(10) = 55 требует 177 вызовов — для одного маленького числа. Дерево вызовов удваивается на каждом уровне.
Вывод: PHP-скрипт
<?php
function fib(int $n, int &$calls): int {
$calls++;
if ($n < 2) {
return $n;
}
return fib($n - 1, $calls) + fib($n - 2, $calls);
}
$calls = 0;
echo "fib(10) = ", fib(10, $calls), "\n";
echo "вызовов функции: ", $calls, "\n";
Почему это взрывается
Посмотрите на число вызовов по мере роста n шагами по 5. Оно растёт не шагами — оно умножается. Каждое +1 к n даёт примерно ×1,6 к числу вызовов; каждое +5 — более чем ×10.
При n = 50 счётчик перевалил бы за 40 миллиардов вызовов. В этом и состоит экспоненциальная ловушка: код выглядит безобидно, а небольшие тесты проходят мгновенно.
Считаем вызовы по мере роста n
От fib(5) до fib(25) входное значение растёт в 5 раз — а число вызовов растёт более чем в 16 000 раз, с 15 до 242 785.
Вывод: PHP-скрипт
<?php
function fib(int $n, int &$calls): int {
$calls++;
if ($n < 2) {
return $n;
}
return fib($n - 1, $calls) + fib($n - 2, $calls);
}
foreach ([5, 10, 15, 20, 25] as $n) {
$calls = 0;
fib($n, $calls);
printf("fib(%2d) -> %7d вызовов\n", $n, $calls);
}
Решение: цикл
Проблема не в числах Фибоначчи — она в том, что одни и те же значения вычисляются много раз. Цикл, который идёт вверх от 0 и 1 и хранит только два последних значения, вычисляет каждое число ровно один раз.
Это O(n) по времени и O(1) по памяти: 24 шага вместо 242 785 вызовов для fib(25). Тот же ответ, другой класс роста — именно для этого и нужен анализ алгоритмов.
Числа Фибоначчи через цикл
Две переменные идут вверх по последовательности; каждый проход вычисляет одно новое число. fib(25) = 75025 за 24 шага — рекурсивной версии для того же ответа потребовалось 242 785 вызовов.
Вывод: PHP-скрипт
<?php
$n = 25;
$steps = 0;
$a = 0;
$b = 1;
for ($i = 2; $i <= $n; $i++) {
[$a, $b] = [$b, $a + $b];
$steps++;
}
echo "fib(25) = ", $b, "\n";
echo "шагов цикла: ", $steps, "\n";