algorithm - フィボナッチアルゴリズムの分析

Question

以下に示すフィバノッチ数プログラムの分析を読んでいます。この実装は非効率的であることが言及されています。実際、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) を計算するために F(n+1) 回の再帰呼び出しが必要です。つまり、f(10)=55 を計算するには、89 回の再帰呼び出しが必要で、89 回が F(11) です。

Answer 2

N 番目のフィボナッチ数 F(n)=F(n-1)+F(n-2) を計算したい場合は、反復法と再帰法で計算できます。反復法でそれを行う場合

#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 投稿からフィボナッチ数列の計算の複雑さ

プログラムの複雑さはbigoh(2power(n))とほぼ同じです。O(n) < O(2powerN) であるため、再帰的な方法は効率的ではありません。

Answer 3

つまり、10 個の数値のフィボナッチ数を計算するには、再帰を 10+1 回実行する必要があります。このタイムラインを改善できるさまざまなアルゴリズムがあります。

フィボナッチ数を見つけることの時間の複雑さとその改善について説明しているこの投稿を見てください:フィボナッチ数列の計算の複雑さ

Answer 4

これがフィボナッチの私のアルゴリズムです

#include<stdio.h>

main()
{
    // If we walk backwards in the fibonacci series, the values before
    // zero will be 1 and -1. i.e the series can be re imagined as 
    // -1, 1, 0, 1, 1, 2, 3.
    // This will spare us from adding special handling for first 
    // and second element of the series  
    int a=-1,b=1,c,i,n;
    printf("enter the limit of series\n");
    scanf("%d",&n);
    printf("The series is : ");
    for(i=1;i<=n;i++)
    {
        c=a+b;
        printf("%d\n",c);
        // move a and b forward
        a=b;
        b=c;
    }
}