为什么计算斐波纳契数列2 ^ n和不是n ^ 2的复杂性? [英] Why is the complexity of computing the Fibonacci series 2^n and not n^2?
问题描述
我想用递归树来寻找斐波那契数列的复杂性,并得出结论树的高度= O(N)
最坏的情况下,成本每个级别= CN
,所以的复杂性= N * N = N ^ 2
I am trying to find complexity of Fibonacci series using a recursion tree and concluded height of tree = O(n)
worst case, cost of each level = cn
, hence complexity = n*n=n^2
为什么是 O(2 ^ n)的
?
推荐答案
在一个天真的递归斐波纳契的复杂性确实2ⁿ。
The complexity of a naive recursive fibonacci is indeed 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ⁿ
In each step you call T
twice, thus will provide eventual asymptotic barrier of:
T(n) = 2⋅2⋅...⋅2 = 2ⁿ
奖金:最好的理论落实到斐波那契数实际上是一个密切公式,使用黄金比例:
bonus: The best theoretical implementation to fibonacci is actually a close formula, using the golden ratio:
Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]
(但是,从现实生活中的precision错误遭受由于浮点算术,这是不准确)
(However, it suffers from precision errors in real life due to floating point arithmetics, which are not exact)
这篇关于为什么计算斐波纳契数列2 ^ n和不是n ^ 2的复杂性?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!