Код: `def fib(n): return n if n<2 else fib(n-1)+fib(n-2)`
Как работает (кратко)
- Для $n<2$ функция возвращает $n$ (базовые случаи).
- Иначе вычисляет рекурсивно $fib(n-1)$ и $fib(n-2)$ и суммирует: $fib(n)=fib(n-1)+fib(n-2)$.
- Это прямая рекурсивная реализация определения чисел Фибоначчи.
Анализ сложности
- Рекуррент для числа вызовов/времени: $T(n)=T(n-1)+T(n-2)+O(1)$. Решение даёт экспоненциальный рост: $T(n)=\Theta ({\phi }^n)$, где $\phi =\frac{1+\sqrt{5}}{2}$ (золотое сечение).
- Пространство (стек вызовов): глубина рекурсии $=O(n)$ (в худшем случае).
- Числовые величины растут экспоненциально: число Фибоначчи $F_n$ имеет длину в битах $\Theta (n)$, поэтому при больших $n$ стоимость арифметики тоже существенна.
Проблемы
- Экспоненциальное время из‑за многократного повторного вычисления одних и тех же подзадач.
- Глубокая рекурсия — риск переполнения стека в Python.
- Нет проверки входных данных (на целое, неотрицательное).
- При больших $n$ арифметика больших целых становится узким местом.
Оптимизации и анализ выигрыша
1) Мемоизация (top‑down)
- Идея: хранить уже вычисленные значения в словаре или использовать `functools.lru_cache`.
- Пример: `@lru_cache(None)\ndef fib(n): return n if n<2 else fib(n-1)+fib(n-2)`
- Сложность: время $O(n)$, память $O(n)$ (таблица + стек).
- Выигрыш: из экспоненциального в линейное — огромный для больших $n$ (примерно фактор $\Theta ({\phi }^n/n)$).
2) Итеративный (bottom‑up) с $O(1)$ памятью
- Идея: пройти от $0$ до $n$, хранить только последние два значения.
- Код: `a,b=0,1\nfor _ in range(n): a,b=b,a+b\nreturn a`
- Сложность: время $O(n)$, память $O(1)$.
- Выигрыш: сравним с мемоизацией по времени, но без затрат на стек и с меньшим потреблением памяти/накладными расходами.
3) Быстрое удвоение (fast doubling)
- Формулы:
$$F_{2k}=F_k(2F_{k+1}-F_k),F_{2k+1}=F_{k+1}^2+F_k^2.$$ - Рекурсивно/итеративно вычисляет $F_n$ за $O(\log n)$ арифметических операций.
- Сложность по операциям: $O(\log n)$. С учётом стоимости умножений больших чисел — $O(M(b)\log n)$, где $b=\Theta (n)$ — длина числа в битах, $M(b)$ — стоимость умножения.
- Выигрыш: асимптотически наилучший по времени для больших $n$ (переход от линейного к логарифмическому числу операций).
4) Матрица + быстрое возведение в степень
- Связь: ${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n$ даёт числа Фибоначчи.
- Используя бинарное возведение в степень — требуемое число матричных умножений $O(\log n)$.
- Сложность и замечания аналогичны быстрому удвоению.
5) Приближённая формула (Бине)
- Формула: $F_n=\frac{{\phi }^n-(-\phi {)}^{-n}}{\sqrt{5}}$. Приближённо можно взять $F_n\approx \mathrm{round}({\phi }^n/\sqrt{5})$.
- Быстро ($O(1)$), но ненадёжно для больших $n$ из‑за погрешностей плавающей арифметики.
Рекомендации
- Для практического использования: для небольших/умеренных $n$ используйте итеративную реализацию (простота + $O(1)$ памяти). Для многократных вызовов — мемоизация.
- Для очень больших $n$ (когда важна скорость) — реализовать fast doubling или матричное экспоненцирование.
- Всегда проверяйте вход (целое неотрицательное) и учитывайте, что арифметика больших целых даёт рост затрат пропорционально длине числа.