Анализ исходного кода
- Рекуррент: $T(n)=T(n-1)+T(n-2)+O(1)$. => время экспоненциально: $T(n)=\Theta ({\phi }^n)$, где $\phi =\frac{1+\sqrt{5}}{2}$.
- Количество вызовов примерно пропорционально $F_{n+1}\sim {\phi }^n/\sqrt{5}$.
- Память (стек) по глубине рекурсии: $S(n)=\Theta (n)$.
Предложения по оптимизации (с оценками и ситуациями применения)
1) Итеративный алгоритм (нижняя динамика, 2 переменные)
- Идея: вычислять последовательно $F_0,F_1,\dots ,F_n$ с двумя переменными.
- Время (арифметические операции): $T(n)=\Theta (n)$. Память: $S(n)=\Theta (1)$.
- Если учитывать размер чисел (битовую сложность), то при больших $n$ число $F_n$ имеет $\Theta (n)$ бит, и суммарная битовая сложность примитивных сложений будет примерно $O(n^2)$.
- Когда применять: простые случаи, ограниченная память, маленькие/умеренные $n$, частые последовательные вычисления (выдача всех $F_k$ до $n$).
2) Мемоизация / динамика с массивом
- Идея: кешировать результаты рекурсивных вызовов (top-down) или хранить массив (bottom-up).
- Время (число вычислений): $T(n)=\Theta (n)$ (каждое значение вычисляется один раз). Память: $S(n)=\Theta (n)$ для кеша (стек при рекурсивной мемоизации может дать ещё $O(n)$ глубины).
- Преимущества: удобна, если вам нужно многократно запрашивать разные $F_k$ с перекрывающимися подзадачами; позволяет восстановить всю последовательность.
- Когда применять: множество запросов на разные $k$ в одном запуске, нужно быстро отвечать на повторные запросы, или требуется доступ к всем предыдущим значениям.
3) Матричный метод / быстрый алгоритм по возведению в степень (включая fast-doubling)
- Идея: ${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n=\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right)$. Использовать возведение в степень за логарифм шагов (деление экспоненты пополам) или формулы fast-doubling:
- fast-doubling: из $F_k,F_{k+1}$ получить $F_{2k}$ и $F_{2k+1}$ за константное число умножений/сложений.
- Число матричных умножений или дублей: $O(\log n)$. Значит арифметических операций $T(n)=\Theta (\log n)$. Память: $S(n)=\Theta (1)$ (или $O(\log n)$ стек при рекурсивной реализации).
- Битовоя сложность с учётом увеличивающегося размера чисел: примерно $O(M(b)\log n)$, где $b=\Theta (n)$ — число бит в $F_n$, и $M(b)$ — сложность умножения больших чисел (для школьного умножения $M(b)=O(b^2)$, для FFT-умножения $M(b)=O(b\log b)$).
- Когда применять: очень большие $n$ (например, $n$ до $10^{12}$ и более), когда нужно получить одно $F_n$ быстро, или при вычислениях по модулю (где числа остаются малыми) — матричный/fast-doubling самый эффективный.
Краткие рекомендации по выбору
- Низкие/умеренные $n$, ограниченная память: итеративный (две переменные).
- Много запросов/нужна вся последовательность: мемоизация или табличный DP.
- Очень большие $n$ или требование к логарифмическому времени (особенно для одного $F_n$ или при работе по модулю): матричный метод / fast-doubling.
Дополнительно
- Неиспользовать рекурсивную экспоненциальную версию в реальных задачах — она годится только для иллюстрации.
- Для приближённых вычислений можно использовать формулу Бине, но она неточна для больших $n$ из-за потери точности в плавающей арифметике.