Кратко: исходная функция вычисляет числа Фибоначчи динамическим заполнением массива.
Что делает код
- Заполняет массив длины $(n+1)$ по рекурренте $F_i=F_{i-1}+F_{i-2}$ и возвращает $F_n$.
- Итерации идут от $2$ до $n$.
Сложность
- Временная: $\mathrm{O}(n)$ (выполняется $n-1$ прибавлений).
- Память: $\mathrm{O}(n)$ (массив размера $(n+1)$).
Альтернативы по памяти и времени
1) Итеративно с константной памятью (простая оптимизация по памяти)
- Память: $\mathrm{O}(1)$.
- Время: $\mathrm{O}(n)$.
Пример:
def fib_const_space(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a + b
return b
2) Быстрый удвоенный метод (fast doubling) или бинарное возведение матрицы
- Время: $\mathrm{O}(\log n)$ по числу больших целочисленных умножений (количество арифметических шагов ~log n).
- Память: $\mathrm{O}(\log n)$ рекурсивно или $\mathrm{O}(1)$ итеративно.
Короткий рекурсивный вариант (fast doubling):
def fib_fast_doubling(n):
if n == 0:
return (0, 1)
(a, b) = fib_fast_doubling(n // 2)
c = a * (2*b - a)
d = a*a + b*b
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)
# F_n = fib_fast_doubling(n)[0]
3) Формула Бине (приближённо)
- Быстро ($\mathrm{O}(1)$), но неточно для больших $n$ из‑за потерь точности плавающей точки; не подходит для точного целого результата при больших $n$.
Учёт переполнения (overflow)
- В Python встроенные целые числа произвольной длины, поэтому переполнение не происходит, но стоимость арифметики растёт с длиной чисел (количество бит ~$\Theta (n)$, т.е. число бит у $F_n$ примерно $n{\log }_2\phi$).
- В языках со фиксированной арифметикой (C, Java):
- использовать библиотеки больших целых (BigInteger, GMP) для точного результата;
- либо вычислять по модулю $m$, если нужен результат по модулю (тогда применяйте % m в операциях; fast doubling легко адаптируется).
Пример с модулем:
def fib_mod(n, m):
if n == 0:
return 0
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, (a + b) % m
return b % m
Замечания по производительности для очень больших n
- Для больших n выгоднее fast doubling: число арифметических операций ~$\Theta (\log n)$, но каждое умножение — над очень длинными числами (битовая длина ~$\Theta (n)$), так что реальная сложность зависит от сложности умножения больших целых.
- Если нужен только результат по модулю, берите fast doubling + взятие по модулю, тогда временная сложность выражается в терминах операций над машинными числами и будет близка к $\mathrm{O}(\log n)$.
Выводы кратко
- Оригинал: время $\mathrm{O}(n)$, память $\mathrm{O}(n)$.
- Для экономии памяти: итеративно с двумя переменными → память $\mathrm{O}(1)$.
- Для ускорения: fast doubling или матрицы → время $\mathrm{O}(\log n)$.
- Для переполнения: в Python проблем нет (использовать BigInt), в языках с фикс. размером — использовать BigInteger/GMP или считать по модулю.