Коротко и формально.
1) Наивный рекурсивный алгоритм (без мемоизации). Пусть $T_{\text{naive}}(n)$ — число операций. Он удовлетворяет рекурренте
$$T_{\text{naive}}(n)=T_{\text{naive}}(n-1)+T_{\text{naive}}(n-2)+\Theta (1),$$ откуда
$$T_{\text{naive}}(n)=\Theta ({\phi }^n),$$ где $\phi =\frac{1+\sqrt{5}}{2}$ (экспоненциальная сложность). Память стекa рекурсии — $\Theta (n)$ в худшем случае (глубина рекурсии).
2) Рекурсивный алгоритм с мемоизацией. Состояния — целые $0,\dots ,n$. Каждый индекс $k$ вычисляется не более одного раза и затем берётся из таблицы. Если операции объединения/листинки и доступ к таблице — $\Theta (1)$ (массив или хэш), то общее время
$$T_{\text{memo}}(n)=\Theta (n).$$ Память для таблицы мемоизации — $\Theta (n)$. Плюс стек рекурсии (топ‑даун) — глубина $\Theta (n)$, итого память $\Theta (n)$.
Если доступ к мемо‑таблице стоит $\Theta (\log n)$ (напр., сбалансированное дерево), тогда время станет $\Theta (n\log n)$.
3) Формальное сравнение и когда мемоизация даёт существенный выигрыш.
- Выигрыш по времени: из экспоненциального $\Theta ({\phi }^n)$ в линейное $\Theta (n)$ — существенное (экспоненциальное ускорение), потому что у задачи много перекрывающихся подзадач.
- Условия эффективности мемоизации:
- есть много перекрывающихся подзадач (как в Фибоначчи) — мемоизация критически полезна;
- пространство состояний небольшое (поли/линейно по $n$), чтобы хранить результаты.
- Когда мемоизация не помогает или вредна:
- подзадачи почти не пересекаются (разветвлённая структура без повторов) — накладные расходы на хранение/поиск делают её бесполезной;
- ограничена память или стек (тогда лучше итеративный DP или хранить только нужные состояния).

4) Практические замечания:
- Для вычисления $F_n$ итеративный DP даёт ту же $\Theta (n)$ по времени и меньше констант/риск переполнения стека; можно снизить память до $\Theta (1)$, храня только два последних значения.
- Мемоизация полезна, когда число уникальных состояний $S$ мало по сравнению с числом рекурсивных вызовов у наивного алгоритма: выигрыш ≈ отношение затрат на повторные вычисления к $S$.
Итого: для рекурсивного Fibonacci с мемоизацией время $\Theta (n)$, память $\Theta (n)$; мемоизация даёт существенное улучшение именно при больших перекрывающихся подзадачах (как в Fibonacci).