Fibonacci DP — Визуализатор алгоритмов

Шаг 1:Initial array: dp[0]=0, dp[1]=1. Fill remaining using dp[i] = dp[i-1] + dp[i-2].

Fibonacci DP

Средний
Временная сложность
O(n²)O(n log n)O(n)O(log n)O(1)n →
O(n)

Последовательность Фибоначчи — классический пример динамического программирования. Каждое следующее число равно сумме двух предыдущих: F(n) = F(n-1) + F(n-2).

Как работает алгоритм (табуляция снизу вверх):

1. Создать таблицу для хранения вычисленных значений
2. Задать базовые случаи: F(0) = 0, F(1) = 1
3. Последовательно заполнить таблицу: F(i) = F(i-1) + F(i-2)
4. Вернуть F(n)

Временная сложность: O(n)

Пространственная сложность: O(n) — можно оптимизировать до O(1)

Сравнение:

  • Наивная рекурсия: O(2^n) — экспоненциальная сложность
  • Мемоизация (сверху вниз): O(n)
  • Табуляция (снизу вверх): O(n)

Динамическое программирование позволяет избежать повторных вычислений, сохраняя ранее полученные результаты. Последовательность Фибоначчи — простейший пример применения этой техники.

Похожие алгоритмы

Частые вопросы

Что такое Числа Фибоначчи (Динамическое программирование)?
Последовательность Фибоначчи — классический пример динамического программирования. Каждое следующее число равно сумме двух предыдущих: F(n) = F(n-1) + F(n-2).
Какова сложность Числа Фибоначчи (Динамическое программирование)?
Время (среднее): O(n) · Память: O(n)
Для кого предназначена визуализация Числа Фибоначчи (Динамическое программирование)?
Визуализация Числа Фибоначчи (Динамическое программирование) рассчитана на средний уровень в категории «Динамическое программирование». Полезна для студентов, подготовки к собеседованиям и практического изучения.
Какие алгоритмы связаны с Числа Фибоначчи (Динамическое программирование)?
В той же категории (Динамическое программирование) вы можете изучить: Knapsack 0/1, Longest Common Subsequence. Каждый из них имеет интерактивную визуализацию.