Кратко — только ответ на вопрос.
1) Анализ исходного рекурсивного алгоритма
- Рекуррент: $$T(n)=T(n-1)+T(n-2)+O(1)$$ - Время: экспоненциально, $$T(n)=\Theta ({\phi }^n)$$ где $\phi =\frac{1+\sqrt{5}}{2}$ (часто грубо пишут $O(2^n)$).
- Память: глубина стека рекурсии $=O(n)$. Дополнительной памяти практически нет, но из-за огромного числа вызовов фактическая суммарная работа экспоненциальна.
2) Подходы для ускорения (минимум три). Для каждого — идея, сложность, код (Python) и плюсы/минусы.
A. Итеративный (простая динамика, O(n), O(1) памяти)
- Идея: считать снизу вверх, хранить только два последних значения.
- Время: $$O(n)$$; память: $$O(1)$$.
- Код:
def fib_iter(n):
if n < 2:
return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a + b
return b
- Плюсы: очень прост, мало памяти, быстрая константа.
- Минусы: линейное время при очень больших $n$ может быть медленно (но обычно достаточно для миллионов при быстрых bigint-операциях).
B. Мемоизация / динамическое программирование
- Идея: запоминать уже посчитанные значения, либо сверху вниз (memo) либо снизу вверх (таблица).
- Время: $$O(n)$$ арифметических операций; память: $$O(n)$$ для кэша. Рекурсивный memo даёт дополнительно глубину стека $=O(n)$.
- Код (top-down с lru_cache):
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n < 2:
return n
return fib_memo(n-1) + fib_memo(n-2)
- Или bottom-up (таблица) с теми же сложностями; можно уменьшить память до $$O(1)$$, если хранить только два значения (тогда это эквивалент итеративного).
- Плюсы: лёгкая реализация, полезно при повторных запросах к разным n.
- Минусы: потребляет $$O(n)$$ памяти для хранения таблицы/кэша, рекурсивный вариант — глубина стекa.
C. Матричное возведение в степень / быстрый удвоение (логарифмическое время по числу арифметических операций)
- Идея (матрица): ${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n$ даёт числа Фибоначчи; возведение в степень выполняется через бинарное возведение (exponentiation by squaring).
Эквивалентный и более компактный вариант — формулы быстрого удвоения (fast doubling):
$$F_{2k}=F_k(2F_{k+1}-F_k),F_{2k+1}=F_{k+1}^2+F_k^2.$$ - Время в модели "арифметическая операция = O(1)": $$O(\log n)$$ операций умножения/сложения.
Но реальные числа растут — количество бит в $F_n$ равно $\Theta (n)$. С учётом стоимости умножения больших целых (обозначим её $M(b)$ для $b$-битных чисел), асимптотика битовой сложности становится примерно $$O(M(n)\log n)$$ (наивное умножение даёт $O(n^2\log n)$).
- Код (fast doubling, возвращает (F_n, F_{n+1})):
def fib_fast_doubling(n):
def fd(k):
if k == 0:
return (0, 1)
a, b = fd(k // 2)
c = a * (2 * b - a)
d = a * a + b * b
if k % 2 == 0:
return (c, d)
else:
return (d, c + d)
return fd(n)[0]
- Или матричное возведение:
def mat_mult(A, B):
return (A[0]*B[0] + A[1]*B[2], A[0]*B[1] + A[1]*B[3],
A[2]*B[0] + A[3]*B[2], A[2]*B[1] + A[3]*B[3])
def mat_pow(M, n):
# M as tuple (a,b,c,d) for 2x2 matrix
if n == 1:
return M
if n % 2 == 0:
half = mat_pow(M, n//2)
return mat_mult(half, half)
else:
return mat_mult(mat_pow(M, n-1), M)
def fib_matrix(n):
if n == 0:
return 0
M = (1,1,1,0)
P = mat_pow(M, n-1)
return P[0]
- Плюсы: асимптотически лучшее число арифметических операций — $O(\log n)$. Отлично для очень больших $n$. Fast doubling проще и быстрее на практике, чем явная матрица.
- Минусы: нужно учитывать рост длины целых чисел; при огромных $n$ стоимость умножений больших чисел доминирует. Реализация чуть сложнее, но стандартная.
D. Формула Бине (не рекомендуется для точных больших вычислений)
- Формула: $$F_n=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}},\psi =\frac{1-\sqrt{5}}{2}.$$ - Плюсы: идея O(1) операций в плавающей точке.
- Минусы: потеря точности при больших $n$; требуется высокая точность (многобитная дробная арифметика) чтобы получить точный целый результат, поэтому на практике неэффективна для больших $n$.
3) Резюме и рекомендации
- Для умеренных $n$ (до миллионов цифр не спрашиваем): итеративный метод или bottom-up DP с O(n) — просты и быстры.
- Для частых запросов с разными n: мемоизация удобна.
- Для очень больших $n$ (когда нужно вычислять числа с миллионами бит, или скорость важна): fast doubling / матричное возведение в степень — лучший выбор (логарифм по числу операций, с учётом стоимости big-int умножений).
- Binet/float — только для приблизительных значений или малых $n$.
Если хотите, могу привести готовые проверенные реализации (с тестами производительности) или оценить реальное время для конкретного $n$.