Коротко о поведении и сложности
- Что делает функция: рекурсивно вычисляет число Фибоначчи $F_n$ по определению $F_n=F_{n-1}+F_{n-2}$ с базами $F_0=0,F_1=1$.
- Временная сложность: число вызовов растёт экспоненциально, примерно как золотое сечение $\phi =\frac{1+\sqrt{5}}{2}$. Т.е. время $T(n)=\Theta ({\phi }^n)$ (часто грубо пишут $O(2^n)$).
- Память (стек): глубина рекурсии $\Theta (n)$, т.е. память по стеку $O(n)$.
- Причина плохой масштабируемости: множество одинаковых подзадач (повторные вызовы для одних и тех же аргументов) — рекурсия востановливает уже вычисленные значения заново.
Оптимизации (минимум два подхода) — с оценками плюсов и минусов
1) Мемоизация (top‑down DP, кеш)
- Идея: запоминать результат для каждого аргумента и возвращать из кеша при повторном запросе.
- Сложность: количество уникальных вычислений $=n$, поэтому число операций $O(n)$ (арифметических сложений). Память $O(n)$.
- Плюсы: очень простая модификация (словарь или functools.lru_cache), быстро для средних $n$.
- Минусы: рекурсивная реализация по-прежнему имеет глубину $O(n)$ (риск переполнения стека), память $O(n)$ может быть нежелательна при ограничениях.
2) Итеративный (bottom‑up) с двумя переменными
- Идея: посчитать последовательно от $0$ до $n$, храня только два последних значения.
- Сложность: $O(n)$ арифметических сложений, память $O(1)$.
- Плюсы: простая, без рекурсии (нет проблем со стеком), минимальная память.
- Минусы: для очень больших $n$ время всё ещё линейное; суммарные затраты на операции с большими целыми (числа Фибоначчи растут экспоненциально) учитывают размер чисел.
3) Быстрое удвоение / возведение матрицы в степень (divide and conquer)
- Идея: использовать формулы быстрого удвоения или матрицу ${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n$ и бинарное возведение в степень.
- Сложность по числу арифметических операций: $O(\log n)$ умножений/сложений больших целых.
- Плюсы: асимптотически намного быстрее для больших $n$ (редуцирует число шагов с $n$ до $O(\log n)$).
- Минусы: сложнее в реализации; операции — умножения больших целых, поэтому реальная временная стоимость зависит от сложности умножения целых (при больших $n$ битовая сложность важна).
Дополнение про большие числа
- При больших $n$ величина $F_n$ растёт как $F_n\approx {\phi }^n/\sqrt{5}$, число бит примерно ${\log }_2{F}_n\approx n{\log }_2\phi +O(1)$, то есть размер чисел сам по себе растёт линейно по $n$. Это означает, что оценка «$O(n)$ операций» скрывает стоимость самих арифметических операций (сложение/умножение больших чисел). В битовой модели:
- Итеративный/мемоизируемый подход даёт примерно $O(n^2)$ битовых операций (школьное сложение $O(n)$ выполняется $O(n)$ раз).
- Быстрое удвоение даёт примерно $O(M(n)\log n)$ битовых операций, где $M(n)$ — стоимость умножения больших чисел (например, FFT‑умножение даёт почти $O(n\log n)$).
Краткая рекомендация
- Для обычных задач и средних $n$: используйте мемоизацию или итеративный подход (итеративный предпочтительнее из‑за $O(1)$ памяти).
- Для очень больших $n$ (когда важно асимптотическое ускорение): используйте быстрый алгоритм удвоения/быстрого возведения в степень (matrix power / fast doubling).