Реализации:
- Рекурсивная без мемоизации: $fib(n)=fib(n-1)+fib(n-2)$ с базами $fib(0),fib(1)$.
- Рекурсивная с мемоизацией: при первом вычислении $fib(k)$ сохраняют результат в словаре/массиве и при повторных обращениях возвращают сохранённое значение.
Временная сложность:
- Без мемоизации: рекуррент $T(n)=T(n-1)+T(n-2)+O(1)$ даёт экспоненциальный рост: $T(n)=\Theta ({\phi }^n)$, где $\phi =\frac{1+\sqrt{5}}{2}\approx 1.618$. Число вызовов функции примерно равно $2F_{n+1}-1$ (где $F_k$ — $k$-е число Фибоначчи).
- С мемоизацией: каждый аргумент $k\le n$ вычисляется один раз, поэтому время $T(n)=\Theta (n)$ (с константной накладной на доступ/запись в таблицу).
Пространственная сложность (доп. память + стек):
- Без мемоизации: максимальная глубина стека вызовов $=O(n)$; дополнительных больших структур нет, итого $O(n)$ по глубине стека.
- С мемоизацией: словарь/массив размера $O(n)$ + стек глубиной $O(n)$ (при рекурсивной реализации) → суммарно $O(n)$. (Итеративный вариант может снизить память до $O(1)$.)
Пример, где разница критична:
- Пусть $n=40$. Тогда число вызовов у наивной рекурсии примерно равно $2F_{41}-1$. Численно $F_{41}=165580141$, следовательно вызовов ≈ $331160281$. У мемоизации — вычисляется примерно $n+1=41$ значений.
- На практике наивный вариант становится непригодным уже для $n\gtrsim 30$-$40$ (секунды→минуты→часы), тогда как мемоизованный — линейно быстрый и работает мгновенно для тех же $n$.
Краткий вывод: наивная рекурсия — экспоненциальное время и глубокий стек; мемоизация снижает время до линейного при памяти $O(n)$. Для любых $n$ больше ~30 используйте мемоизацию или итеративный алгоритм.