Корректность
- Функция корректно вычисляет числа Фибоначчи для неотрицательных целых $n$. База: для $n=0$ и $n=1$ возвращается $n$ — это $F_0$ и $F_1$. Индуктивно: если для всех $k<n$ функция возвращает $F_k$, то для $n>1$ она возвращает $F_{n-1}+F_{n-2}=F_n$.
Временная и пространственная сложность
- Время: рекурсия без мемоизации повторяет вычисления экспоненциально. Время роста равно числу вызовов, которое можно выразить как $2F_{n+1}-1$ и асимптотически равно $\Theta ({\phi }^n)$, где $\phi =\frac{1+\sqrt{5}}{2}$ (приблизительно $1.618$).
- Память (стек вызовов): глубина рекурсии равна $n$, значит дополнительная память $O(n)$ (в терминах вызовов/стека). Никакого кеширования промежуточных значений нет, поэтому общая используемая память пропорциональна глубине стека.
Три способа оптимизации (описание, сложность, преимущества и недостатки)
1) Мемоизация (top‑down, например functools.lru_cache)
- Суть: запоминать уже вычисленные значения и возвращать их при повторном запросе.
- Пример: использовать декоратор $\text{@lru\_cache(None)}$ или словарь.
- Сложность: время $O(n)$ (каждое значение $\mathrm{0..}n$ вычисляется один раз), память $O(n)$ для кеша плюс стек глубиной $n$ (если рекурсивно).
- Плюсы: простая правка существующей рекурсивной реализации; легко внедряется.
- Минусы: требует памяти $O(n)$; рекурсивная реализация может упереться в лимит рекурсии Python для больших $n$ (можно переписать в итеративную).
2) Итеративный (bottom‑up) с константной памятью
- Суть: вычислять последовательно $F_0,F_1,\dots ,F_n$, сохраняя только два последних значения.
- Сложность: время $O(n)$, память $O(1)$.
- Плюсы: очень экономная по памяти и быстрая реализация на практике; нет проблем с глубиной стека.
- Минусы: асимптотика времени всё ещё линейная; при большом $n$ число бит в результате растёт (в Python это учитывается автоматически, но арифметика больших целых замедляет работу).
3) Быстрое возведение в степень / fast doubling (алгоритм за логарифм времени)
- Суть: использовать рекурсивные формулы (fast doubling) или возведение матрицы ${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n$ методом возведения в степень по бинарному разложению, чтобы получить $F_n$ за $O(\log n)$ арифметических операций.
- Сложность по числу арифметических операций: $O(\log n)$. Однако при учёте стоимости операций с большими целыми, итоговая битовая сложность зависит от стоимости умножения больших чисел (для $F_n$ длина в битах $\Theta (n)$), поэтому полная оценка — сложнее (при наивном умножении итогово примерно $O(n^2\log n)$ битовых операций; с быстрыми алгоритмами умножения — лучше).
- Плюсы: асимптотически лучшее решение по числу арифметических шагов; выгодно для очень больших $n$.
- Минусы: сложнее в реализации; для умеренных $n$ оверхед констант может сделать его медленнее простого итеративного метода; нужно учитывать стоимость многозначной арифметики.
Краткие практические рекомендации
- Для большинства задач и средних $n$ используйте итеративный алгоритм с двумя переменными (лучшее сочетание простоты и скорости).
- Если нужно многократно запрашивать значения для разных $n$ внутри одного запуска — примените мемоизацию.
- Для очень больших $n$ (или когда важна асимптотика) применяйте fast doubling / матрицы и учитывайте стоимость операций с большими целыми.