2

フィボナッチの「悪い」バージョンが O(2^n) であることを証明するのに苦労しています。すなわち。関数を考えると

int fib(int x)
{
  if ( x == 1 || x == 2 )
  {
    return 1;
  }
  else
  {
    return ( f( x - 1 ) + f( x - 2) );
  }
}

これが O(2^n) であることを証明するための助けを得ることができますか?

4

4 に答える 4

6

ランタイムの再帰関係を書くことから始めましょう:

T(1) = 1

T(2) = 1

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

では、推測してみましょう

T(n) ≤ 2 n

これを帰納法で証明しようとすると、基本ケースは次のようになります。

T(1) = 1 ≤ 2 = 2 1

T(2) = 1 ≤ 4 = 2 2

次に、帰納的なステップで、次のことがわかります。

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

≤ 2 n + 2 n+1 + 1

< 2 n+1 + 2 n+1

= 2n+2

したがって、帰納法により、任意の n について T(n) ≤ 2 nと結論付けることができ、したがって T(n) = O(2 n ) となります。

より正確な分析を行うと、T(n) = 2F n - 1 であることを証明できます。ここで、F nは n 番目のフィボナッチ数です。これは、より正確に、T(n) = Θ(φ n ) であることを証明しています。ここで、φ は黄金比で、約 1.61 です。φ n = o(2 n ) (little-o 表記を使用) であるため、これははるかに優れた境界であることに注意してください。

お役に立てれば！

于 2013-10-15T23:43:22.340 に答える
0

再帰ツリー法を使用する:

                                             T(n)                         
                                       ↙            ↘
                                   n-1              n – 2                                 
                               ↙      ↘             ↙      ↘
                           N – 2      n – 3      n – 3       n - 4

各ツリー レベルは fib(x - 1) fib(x - 2) の呼び出しと見なされます。この方法で再帰ツリーを完了すると、x = 1 または x = 2 (基本ケース) のときに停止します .... これtree は、再帰ツリーの 3 つのレベルのみを示しています。このツリーを解決するには、次の重要な情報が必要です: 1- ツリーの高さ。2-各レベルでの作業量。このツリーの高さは 2^n で、各レベルでの作業は O(1) であり、この繰り返しの順序は 高さ * 各レベルでの作業 = 2^n * 1 = O(2^n) です。

于 2013-10-17T01:09:11.087 に答える
0

いくつかのテスト ケースを手動で実行してみて、メソッドが呼び出されたf(5)回数を記録します。f()

太いヒントは、メソッドが呼び出されるたびにf()(x が 1 または 2 であることを除いて)、f()2 回呼び出されることに注意することです。f()それらのそれぞれは、それぞれさらに2回呼び出します...

于 2013-10-15T23:43:31.847 に答える
0

実際には、 への呼び出しの総数が になるという非常に単純な証明がありfます2Fib(n)-1。ここFib(n)で、 は n 番目のフィボナッチ数です。こんなふうになります：

  1. 二分木を形成する呼び出しのセットf。各呼び出しは葉 (x=1 または x=2 の場合) または 2 つの子呼び出し (x>2 の場合) のいずれかです。
  2. 各リーフは、元の呼び出しによって返された合計にちょうど 1 寄与するため、合計Fib(n)リーフがあります。
  3. 任意のバイナリ ツリーの内部ノードの総数は に等しくL-1、Lは葉の数であるため、このツリーのノードの総数は です2L-1。

これは、実行時間 ( への呼び出しの合計で測定f) が

T(n)=2Fib(n)-1=O(Fib(n))

そして、以来、黄金比はFib(n)=Θ(φ^n)どこにありますかφ 

Φ=(1+sqrt{5})/2 = 1.618...

これはそれを証明しT(n) = Θ(1.618...^n) = O(n)ます。

于 2013-10-16T11:45:22.860 に答える