Коротко — почему неэффективен:
- Рекурсивная функция пересчитывает одни и те же значения много раз (перекрывающиеся подзадачи). Количество вызовов растёт экспоненциально с $n$ (приблизительно как числа Фибоначчи). Конкретно число вызовов ~ $F_{n+1}\sim \frac{{\varphi }^n}{\sqrt{5}}$, где $\varphi =\frac{1+\sqrt{5}}{2}$.
- Из-за этого время выполнения экспоненциальное, а для больших $n$ практически неосуществимо.
Оценки сложностей:
- Временная сложность (наивный рекурсивный алгоритм): $O({\varphi }^n)$ (часто грубо записывают как $O(2^n)$).
- Пространственная сложность (глубина стека рекурсии): $O(n)$.
- Примечание: при очень больших $n$ надо учитывать стоимость операций с большими целыми: значение $F_n$ имеет $\Theta (n)$ бит, поэтому примитивные арифметические операции сами по себе становятся дорогими.
Три способа оптимизации (с примерами, преимуществами и ограничениями):
1) Мемоизация (Top‑down DP)
- Идея: запоминать уже вычисленные $F_k$ и возвращать их вместо повторного вычисления.
- Пример (Python):
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n < 2:
memo[n] = n
else:
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
Или кратко: from functools import lru_cache; @lru_cache(None) def fib(n): ...
- Временная сложность: $O(n)$ (каждое значение $\mathrm{0..}n$ вычисляется один раз).
- Пространственная: $O(n)$ для хранения таблицы + $O(n)$ глубина стека (если рекурсивно).
- Преимущества: очень просто внедрить; быстро для средних $n$.
- Ограничения: рекурсивная глубина остаётся $O(n)$ (можно переписать итеративно, чтобы убрать стек); память $O(n)$.
2) Итеративный (Bottom‑up) с константной памятью
- Идея: вычислять последовательно от $0$ до $n$, храня только последние два значения.
- Пример:
def fib_iter(n):
if n < 2:
return n
a, b = 0, 1
for _ in range(n-1):
a, b = b, a + b
return b
- Временная сложность: $O(n)$.
- Пространственная сложность: $O(1)$ (помимо места для результата).
- Преимущества: простота, нет рекурсии, малое потребление памяти.
- Ограничения: всё ещё линейное время; при очень больших $n$ затратны операции с большими целыми.
3) Быстрое возведение в степень / fast doubling (логарифмическое время)
- Идея 1 (матрицы): использовать ${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n$ — возведение матрицы за $O(\log n)$ умножений матриц.
- Идея 2 (fast doubling, формулы):
$F_{2k}=F_k(2F_{k+1}-F_k)$,
$F_{2k+1}=F_{k+1}^2+F_k^2$.
- Пример (fast doubling):
def fib_fast(n):
def fd(n):
if n == 0:
return (0, 1)
(a, b) = fd(n // 2)
c = a * (2*b - a)
d = a*a + b*b
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)
return fd(n)[0]
- Временная сложность (в терминах арифметических операций): $O(\log n)$ умножений/сложений больших чисел.
- Пространственная: рекурсивная глубина $O(\log n)$ (можно сделать итеративно).
- Преимущества: значительно быстрее для очень больших $n$; логарифмическое количество операций.
- Ограничения: операции с большими целыми остаются дорогими — учитывая размер чисел (они имеют $\Theta (n)$ бит), стоимость умножений/сложений нужно учитывать в оценке по битовым операциям; для экстремально больших $n$ нужны оптимизации арифметики (FFT‑умножение) или вычисление по модулю.
Краткое резюме:
- Наивный рекурсивный алгоритм экспоненциален: $O({\varphi }^n)$, глубина стека $O(n)$.
- Простые и эффективные улучшения: мемоизация (O(n) время, O(n) память), итеративный счёт (O(n) время, O(1) память), fast doubling / матрицы (O(\log n) операций — лучшая по времени при больших $n$). Выбор зависит от $n$ и ограничений по памяти / точности / арифметике.