为什么计算Fibonacci系列2 ^ n而不是n ^ 2的复杂性？

Question

我试图找到使用递归树的Fibonacci系列的复杂性,并因此得出height of tree = O(n)最坏情况cost of each level = cncomplexity = n*n=n^2

怎么回事O(2^n)？

Answer 1

天真的递归斐波纳契的复杂性确实是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]

(但是,由于浮点算术,它在现实生活中会出现精度误差,这并不精确)

Answer 2

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  

1. 在2 ^(n-1)中使用n-1,因为对于fib(5),我们最终将归结为fib(1)
2. 内部节点数=叶数 - 1 = 2 ^(n-1) - 1
3. 加法数=内部节点数+叶数=(2 ^ 1 + 2 ^ 2 + 2 ^ 3 + ...)+ 2 ^(n-1)
4. 我们可以将内部节点的数量替换为2 ^(n-1) - 1,因为它总是小于这个值:= 2 ^(n-1) - 1 + 2 ^(n-1)~2 ^ n

Answer 3

像这样看待它.假设通过递归计算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是正确的.

Answer 4

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 ^ n
它将使总时间复杂度=> 2 + 4 + 8 + ..... 2 ^ n在求解上述gp后我们得到时间复杂度为O(2 ^ n)

Answer 5

你是正确的,树的深度是O(n),但你没有在每个级别做O(n)工作.在每个级别,每个递归调用执行O(1)工作,但每个递归调用然后提供两个新的递归调用,一个在它下面的级别,一个在它下面的二级.这意味着随着您在递归树中越走越远,每个级别的调用数量呈指数级增长.

有趣的是,您实际上可以确定计算F(n)所需的确切调用次数为2F(n + 1) - 1,其中F(n)是第n个Fibonacci数.我们可以归纳地证明这一点.作为基本情况,要计算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'<n,n≥2,L(n')= 2F(n + 1) - 1.然后计算F(n),我们需要使1调用计算F(n)的初始函数,该函数依次触发对F(n-2)和F(n-1)的调用.通过归纳假设,我们知道F(n-1)和F(n-2)可以在L(n-1)和L(n-2)次调用中计算.因此,总运行时间是

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

这完成了归纳.

此时,您可以使用Binet的公式来显示

L(n)= 2(1 /√5)(((1 +√5)/ 2)ⁿ - ((1 - √5)/ 2)ⁿ) - 1

因此L(n)= O(((1 +√5)/ 2)ⁿ).如果我们使用那个惯例

φ=(1 +√5)/2≈1.6

我们有

L(N)=Θ(φ ^Ñ)

并且由于φ<2,这是o(2 ⁿ)(使用少量符号).

有趣的是,我为这个系列选择了名字L(n),因为这个系列被称为莱昂纳多数字.除了在这里使用之外,它还出现在smoothsort算法的分析中.

希望这可以帮助!