Пример типичного кода с рекурсией и мемоизацией (две реализации):
1) С помощью lru_cache:
```python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
```
2) С помощью словаря:
```python
def fib(n, memo={}):
if n < 2:
return n
if n in memo:
return memo[n]
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
```
Анализ по времени и по памяти
- Количество уникальных вычислений: каждый индекс $\mathrm{0..}n$ вычисляется не более одного раза, значит число вызовов/сложений — $O(n)$. В терминах сложностной нотации: время по числу операций сложения/доступов — $O(n)$.
- Однако числа Фибоначчи растут экспоненциально, их битовая длина примерно
$\sim n{\log }_2\phi$, где $\phi =(1+\sqrt{5})/2$. Поэтому стоимость одной операции сложения/умножения зависит от размера чисел. В битовой модели:
- сложение $O(n)$ бит,
- умножение $O(M(n))$ бит (где $M(n)$ — стоимость умножения n-битных чисел).
Тогда общая битовая сложность рекурсивной мемоизированной реализации примерно $O(n^2)$ при использовании наивного сложения/учёта роста длин (точнее, сумма размеров хранимых чисел даёт $O(n^2)$ битовых операций).
- Память (RAM):
- количество хранимых значений в memo — $O(n)$ объектов (каждое — целое число),
- глубина рекурсии — $O(n)$ (стек вызовов),
- в битах суммарный объём для всех сохранённых чисел ~ сумма битовых длин $=O(n^2)$ бит.
Итого: по объектам/записям — $O(n)$, по битам/байтам — $O(n^2)$ из‑за роста размеров чисел.
Практические проблемы данной реализации
- Рекурсия в Python: стек ограничен (обычно ~1000), для больших $n$ будет RecursionError.
- Кеш (lru_cache или dict) хранит все вычисленные значения, что может потреблять много памяти для больших $n$.
- Для очень больших $n$ время ограничено не количеством операций, а стоимостью операций на больших целых числах.
Предложения по улучшению
1) Итеративная версия с O(1) дополнительной памяти и без рекурсии (рекомендуется для большинства задач):
```python
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
```
- Время по операциям: $O(n)$.
- Память: $O(1)$ целых (но сами целые растут по битам).
2) Быстрое удвоение (fast doubling) — асимптотически быстрее по числу арифметических операций, рекурсия глубиной $O(\log n)$:
```python
def fib_fast_doubling(n):
def fd(k):
if k == 0:
return (0, 1)
a, b = fd(k >> 1)
c = a * (2*b - a)
d = a*a + b*b
if k & 1:
return (d, c + d)
else:
return (c, d)
return fd(n)[0]
```
- Количество больших умножений/сложений ~ $O(\log n)$.
- Битовая сложность примерно $O(M(n)\log n)$ (где $M(n)$ — стоимость умножения n-битных чисел). При наивном умножении $M(n)=O(n^2)$, с улучшенными алгоритмами умножения сложность снижается.
3) Для единственного большого $n$ — использовать fast doubling или матричное возведение в степень (экспоненциация по модулю или для целых с быстрым умножением). Для множества запросов с разными $n$ — выгодно кэшировать результаты (но контролировать размер кеша).
4) Практические замечания:
- Избегайте рекурсии для $n\gtrsim 1000$ в Python (ошибки стека).
- Если память ограничена, используйте итеративный вариант с двумя переменными.
- Для очень больших $n$ (много сотен тысяч цифр) используйте fast doubling и полагайтесь на оптимизации умножения больших целых в интерпретаторе (CPython использует разные алгоритмы, включая FFT для очень больших чисел).
Короткая рекомендация:
- Нужна простота и $n$ не очень велико → итеративный цикл.
- Нужен самый быстрый асимптотический алгоритм для огромного $n$ → fast doubling (или специализированные библиотеки для больших чисел).