Почему сложность вычисления ряда Фибоначчи 2^n, а не n^2?
Я пытаюсь найти сложность ряда Фибоначчи, используя дерево рекурсии, и пришел к выводу height of tree = O(n) худший случай, cost of each level = cnотсюда complexity = n*n=n^2
Как это так O(2^n)?
9 ответов
Сложность наивного рекурсивного фибоначчи действительно равна 2ⁿ.
T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) =
= T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...
На каждом этапе вы звоните T в два раза, тем самым обеспечит возможный асимптотический барьер:T(n) = 2⋅2⋅...⋅2 = 2ⁿ
Бонус: лучшая теоретическая реализация Фибоначчи - это на самом деле близкая формула, использующая золотое сечение:
Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]
(Тем не менее, он страдает от ошибок точности в реальной жизни из-за арифметики с плавающей запятой, которые не являются точными)
Дерево рекурсии для fib (n) будет выглядеть примерно так:
n
/ \
n-1 n-2 --------- maximum 2^1 additions
/ \ / \
n-2 n-3 n-3 n-4 -------- maximum 2^2 additions
/ \
n-3 n-4 -------- maximum 2^3 additions
........
-------- maximum 2^(n-1) additions
- Используя n-1 в 2 ^ (n-1), так как для fib(5) мы в конечном итоге перейдем к fib (1)
- Количество внутренних узлов = Количество листьев - 1 = 2 ^ (n-1) - 1
- Количество сложений = Количество внутренних узлов + Количество листьев = (2^1 + 2^2 + 2^3 + ...) + 2^(n-1)
- Мы можем заменить число внутренних узлов на 2 ^ (n-1) - 1, потому что оно всегда будет меньше этого значения: = 2^(n-1) - 1 + 2^(n-1) ~ 2^n
Вы правы, что глубина дерева составляет O(n), но вы не выполняете O (n) работу на каждом уровне. На каждом уровне вы выполняете O(1) работу за рекурсивный вызов, но каждый рекурсивный вызов вносит два новых рекурсивных вызова, один на уровне ниже его и один на уровне два ниже него. Это означает, что по мере продвижения вниз и ниже по дереву рекурсии количество вызовов на уровень растет в геометрической прогрессии.
Интересно, что на самом деле вы можете установить точное количество вызовов, необходимое для вычисления F (n), как 2F (n + 1) - 1, где F (n) - это n-е число Фибоначчи. Мы можем доказать это индуктивно. В качестве базового случая для вычисления F(0) или F (1) нам нужно сделать ровно один вызов функции, который завершается без каких-либо новых вызовов. Допустим, что L(n) - это количество вызовов, необходимых для вычисления F(n). Тогда у нас есть это
L (0) = 1 = 2 * 1 - 1 = 2F (1) - 1 = 2F (0 + 1) - 1
L (1) = 1 = 2 * 1 - 1 = 2F (2) - 1 = 2F (1 + 1) - 1
Теперь для индуктивного шага предположим, что для всех n' 1 + L(n - 1) + L(n - 2) = 1 + 2F ((n - 1) + 1) - 1 + 2F ((n - 2) + 1) - 1 = 2F (n) + 2F (n - 1) - 1 = 2 (F (n) + F (n - 1)) - 1 = 2 (F (n + 1)) - 1 = 2F (n + 1) - 1 Что завершает индукцию. На данный момент, вы можете использовать формулу Бине, чтобы показать, что L(n) = 2 (1 / √5) (((1 + √5) / 2)n - ((1 - √5) / 2)n) - 1 И, таким образом, L(n) = O (((1 + √5) / 2)n). Если мы используем соглашение, которое φ = (1 + √5) / 2 ≈ 1.6 У нас есть это L(n) = Θ (φn) А так как φ < 2, это o (2 n) (используя обозначения little-o). Интересно, что я выбрал название L(n) для этой серии, потому что эта серия называется числами Леонардо. Помимо его использования здесь, он возникает при анализе алгоритма сглаживания. Надеюсь это поможет!
t(n)=t(n-1)+t(n-2), который может быть решен методом дерева:
t(n-1) + t(n-2) 2^1=2
| |
t(n-2)+t(n-3) t(n-3)+t(n-4) 2^2=4
. . 2^3=8
. . .
. . .
аналогично для последнего уровня., 2^ п
общая сложность по времени =>2+4+8+.....2^n после решения вышеупомянутого gp мы получим сложность по времени как O(2^n)
Посмотри на это так. Предположим, сложность расчета F(k), kth Число Фибоначчи по рекурсии не более 2^k за k <= n, Это наша индукционная гипотеза. Тогда сложность расчета F(n + 1) по рекурсии
F(n + 1) = F(n) + F(n - 1)
который имеет сложность 2^n + 2^(n - 1), Обратите внимание, что
2^n + 2^(n - 1) = 2 * 2^n / 2 + 2^n / 2 = 3 * 2^n / 2 <= 2 * 2^n = 2^(n + 1).
По индукции мы показали, что утверждение о F(k) по рекурсии не более 2^k верно.
Сложность ряда Фибоначчи составляет O(F(k)), где F (k) - это k-е число Фибоначчи. Это можно доказать по индукции. Это тривиально для обоснованного случая. И предположим, что для всех k<=n сложность вычисления F (k) равна c*F(k) + o(F(k)), тогда для k = n+1 сложность вычисления F (n + 1)) это c*F(n) + o(F(n)) + c*F(n-1) + o(F(n-1)) = c*(F(n) + F(n-1)) + o(F(n)) + o(F(n-1)) = O(F(n+1)).
Сложность рекурсивных рядов Фибоначчи составляет 2^n:
Это будут рекуррентные соотношения для рекурсивного Фибоначчи
T(n)=T(n-1)+T(n-2) No of elements 2
Теперь о решении этого отношения с использованием метода подстановки (подстановка значений T(n-1) и T(n-2))
T(n)=T(n-2)+2*T(n-3)+T(n-4) No of elements 4=2^2
Снова подставив значения указанного выше термина, получим
T(n)=T(n-3)+3*T(n-4)+3*T(n-5)+T(n-6) No of elements 8=2^3
После полного решения проблемы мы получаем
T(n)={T(n-k)+---------+---------}----------------------------->2^k eq(3)
Это подразумевает, что максимальное количество рекурсивных вызовов на любом уровне не будет превышать 2^n.
И для всех рекурсивных вызовов в уравнении 3 ϴ(1), поэтому сложность времени будет 2^n* ϴ(1)=2^n
Сложность O(2^n) вычисления числа Фибоначчи применима только к рекурсивному подходу. С небольшим дополнительным пространством вы можете добиться гораздо лучшей производительности с O(n).
public static int fibonacci(int n) throws Exception {
if (n < 0)
throws new Exception("Can't be a negative integer")
if (n <= 1)
return n;
int s = 0, s1 = 0, s2 = 1;
for(int i= 2; i<=n; i++) {
s = s1 + s2;
s1 = s2;
s2 = s;
}
return s;
}
Я не могу устоять перед искушением соединить итеративный алгоритм линейного времени для Fib с рекурсивным экспоненциальным временем: если кто-то читает замечательную небольшую книгу Джона Бентли "Написание эффективных алгоритмов", я считаю, что это простой случай "кэширования": всякий раз, когда Fib (k) вычисляется, хранится в массиве FibCached[k]. Каждый раз, когда вызывается Fib(j), сначала проверьте, кэшируется ли он в FibCached[j]; если да, вернуть значение; если не использовать рекурсию. (Посмотрите на дерево звонков сейчас...)