Анализ исходного кода
- Рекуррентное соотношение времени: $T(n)=T(n-1)+T(n-2)+\Theta (1)$. Решение даёт экспоненциальный рост: $T(n)=\Theta ({\phi }^n)$, где $\phi =\frac{1+\sqrt{5}}{2}$.
- По памяти: глубина рекурсии и стек вызовов $S(n)=\Theta (n)$. (Количество вызовов примерно $2F_{n+1}-1$.)
Способы оптимизации (минимум три), с идеей, сложностью и кодом.
1) Мемоизация (топ‑down DP)
- Идея: запоминать результаты подзадач, чтобы не пересчитывать.
- Время: $\mathrm{O}(n)$ (число уникальных вызовов), память: $\mathrm{O}(n)$ для кеша (плюс рекурс. стек $\mathrm{O}(n)$).
- Код:
from functools import lru_cache
@lru_cache(None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n-1) + fib_memo(n-2)
2) Итеративный (bottom‑up) с O(1) памяти
- Идея: вычислять снизу вверх, храня только два последних значения.
- Время: $\mathrm{O}(n)$, память: $\mathrm{O}(1)$.
- Код:
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
3) Быстрое удвоение (fast doubling) — O(log n)
- Идея: использовать рекурсивные формулы
$$F_{2k}=F_k(2F_{k+1}-F_k),F_{2k+1}=F_{k+1}^2+F_k^2$$ и вычислять по двоичному разложению n за логарифм шагов.
- Время: $\mathrm{O}(\log n)$ (считая арифметику за O(1)); память: рекурс. стек $\mathrm{O}(\log n)$ (можно сделать итеративно для $\mathrm{O}(1)$).
- Код:
def fib_fast_doubling(n):
def fd(n):
if n == 0:
return (0, 1)
a, b = fd(n // 2)
c = a * (2*b - a)
d = a*a + b*b
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)
return fd(n)[0]
Доп. вариант: матричное возведение в степень (матрица ${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n$) даёт тоже $\mathrm{O}(\log n)$ времени через возведение в степень по бинарному возведению; полезно, если реализовать на целых числах или с оптимизированной матричной арифметикой.
Примечания
- Для очень больших $n$ учитывать стоимость операций с большими целыми числами: реальная стоимость сложения/умножения влияет на асимптотику (вместо «констант» появляется сложность арифметики).
- Самые практичные решения: итеративный (простота, $\mathrm{O}(1)$ памяти) и fast doubling (лучшее асимпт. время $\mathrm{O}(\log n)$).