fibonacci算法分析

Question

我正在阅读一个fibanocci数字程序的分析，如下所示。有人提到这种实现是低效的。实际上，计算Fn的递归调用次数是F(n+1)。

我的问题是：“计算Fn的递归调用数是F(n+1)”是什么意思？

int F(int i)
{ 
  if (i < 1) return 0;
  if (i == 1) return 1;
  return F(i-1) + F(i-2);
}

Answer 1

计算斐波那契数的朴素实现采用F(n+1)递归调用来计算数字F(n)；即，要计算f(10)=55，您需要89个递归调用，其中89个是F(11)。

Answer 2

如果要计算第N个斐波那契数F(n)=F(n-1)+F(n-2)，.We可以用迭代法和递归法来实现。如果我们使用迭代法

#include<stdio.h>

main()
{
int a=0,b=1,c,i,n;
//clrscr();
printf("enter the limit of series\n");
scanf("%d",&n);
if(n==0)
printf("%d\n",a);
else
printf("%d\n%d\n",a,b);
for(i=2;i<=n;i++)
{
c=a+b;
printf("%d\n",c);
a=b;
b=c;
}

}

从i=0迭代到N需要O(n)时间。

而是使用递归方法

int F(int i)
  { 
    if (i < 1) return 0;
    if (i == 1) return 1;
    return F(i-1) + F(i-2);
  }

递归关系为

                     ___________ 0 if(n<=0) 
                    /___________ 1 if(n==1)
  Fibonacci(n) ____/
                   \
                    \___________ Fibonacci(n-1)+Fibonacci(n-2) 

因此，我们的问题n= (n-1)的子问题+ (n-2)的子问题，因此我们的时间函数T(n)如下

   T(n)=T(n-1)+T(n-2)+O(1)
   T(n)={T(N-2)+T(n-3)}+T(n-2)  since T(n-1)=T(n-2)+T(n-3) -------- equation(1)
   from above you can see T(n-2) is calculated twice. If we expand the recursion tree for N=5 . The recursion tree is as follows


                                                       Fib(5)
                                                          |
                                    _____________________/ \__________________
                                   |                                          |
                                 Fib(4)                   +                 fib(3)    
                                   |                                          |
                           _______/ \_______                         ________/ \_______
                          |        +        |                        |        +        |
                       Fib(3)             Fib(2)                   Fib(2)           Fib(1)
                          |                  |                        |                
                  _______/ \____        ____/ \_______        _______/ \_____                   
                 |        +     |      |     +        |      |         +      |   
              Fib(2)        Fib(1)    Fib(1)      Fib(0)     Fib(1)        Fib(0)
         _______/ \_______
        |        +        |
      Fib(1)             Fib(0)

如果我们观察递归树，我们发现Fib(1)被计算5次，Fib(2)被计算3次，Fib(3)被计算2次

所以使用递归，我们实际上是在做冗余的计算。如果您使用迭代方法，则可以避免这些冗余计算。

T(n)=T(n-1)+T(n-2)+1

来自上一篇SO post Computational complexity of Fibonacci Sequence

程序的复杂度近似为=(2power(N))。由于O(n) < O(2powerN)递归方法效率不高。

Answer 3

“程序的复杂度大约等于(2power(N))。由于O(n) < O(2powerN)递归方法效率不高。”

如果他们根据所需的递归调用数量来计算这种复杂性，那么我不知道他们从哪里获得2^n。该图根本不会对2^n进行建模，对于更大的值，建模会显著衰减。到832,040的第30项，计算它需要2,692,536次递归调用，远远少于超过10亿的2^30次。不到1%！