Когда работа удваивается
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 вызовов — ради одного небольшого числа. Дерево вызовов удваивается на каждом уровне.
Вывод: полная программа на Python
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print("fib(10) =", fib(10))
print("вызовов функции:", calls)
Почему происходит взрыв
Следите за количеством вызовов, когда n растёт с шагом 5. Оно растёт не на шаг — оно умножается. Каждое +1 к n даёт примерно ×1,6 к числу вызовов; каждое +5 — больше чем ×10.
При n = 50 количество превысило бы 40 миллиардов вызовов. В этом и состоит экспоненциальная ловушка: код выглядит безобидно, а небольшие тесты завершаются мгновенно.
Подсчёт вызовов при росте n
От fib(5) до fib(25) входные данные растут в 5 раз — а количество вызовов растёт более чем в 16 000 раз, с 15 до 242 785.
Вывод: полная программа на Python
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
for n in [5, 10, 15, 20, 25]:
calls = 0
fib(n)
print(f"fib({n:2d}) -> {calls:7d} вызовов")
Решение: цикл
Проблема не в Фибоначчи — она в том, что одни и те же значения вычисляются снова и снова. Цикл, который поднимается от 0 и 1 и хранит только два последних значения, вычисляет каждое число ровно один раз.
Это время O(n) и память O(1): 24 шага вместо 242 785 вызовов для fib(25). Тот же ответ, другой класс роста — именно для этого и нужен анализ алгоритмов.
Фибоначчи с циклом
Две переменные поднимаются по последовательности; каждый проход вычисляет одно новое число. fib(25) = 75025 за 24 шага — рекурсивной версии для того же ответа понадобилось 242 785 вызовов.
Вывод: полная программа на Python
n = 25
steps = 0
a, b = 0, 1
for i in range(2, n + 1):
a, b = b, a + b
steps += 1
print("fib(25) =", b)
print("шагов цикла:", steps)