1

だから、私はJavaで'n番目のフィボナッチ数を取得するための再帰メソッドを持っています-私が持っている唯一の質問は、時間計算量は何ですか？O（2 ^ n）だと思いますが、間違えたのでは？（反復がはるかに優れていることは知っていますが、それは演習です）

public int fibonacciRecursive(int n)
{
    if(n == 1 || n == 2) return 1;
    else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
}
4

5 に答える 5

5

再帰コードには指数関数的な実行時間があります。しかし、ベースは2ではないと思いますが、おそらく黄金比（約1.62）です。しかしもちろん、O（1.62 ^ n）も自動的にO（2 ^ n）になります。

実行時間は再帰的に計算できます。

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

これは、フィボナッチ数自体の再帰的定義と非常によく似ています。再帰方程式の+1inは、nが大きい場合はおそらく無関係です。SIは、それがfibo数とほぼ同じ速さで成長し、それらは黄金比をベースとして指数関数的に成長すると考えています。

メモ化を使用して、つまり、すでに計算された結果をキャッシュすることで、速度を上げることができます。次に、反復バージョンと同じようにO（n）ランタイムがあります。

反復コードの実行時間はO（n）です。

O（n）ステップと各反復の一定時間の単純なループがあります。

于 2011-01-22T15:47:50.853 に答える
5

あなたはこれを使うことができます

代替テキスト

O（log n）でFnを計算するには

于 2011-01-22T16:18:38.230 に答える
3

各関数呼び出しは、正確に1つの加算を実行するか、1を返します。基本ケースは値1のみを返すため、加算の総数はfib（n）-1です。したがって、関数呼び出しの総数は2 * fib（n）-1であるため、時間計算量はΘ（fib（N））=Θ（phi ^ N）であり、これはO（2 ^ N）によって制限されます。

于 2011-01-22T15:59:55.047 に答える
0

O（2 ^ n）？ここにはO（n）しか見えません。

なぜこれらを計算して再計算し続けるのだろうか？メモリ要件があまりにも不快にならない限り、あなたが持っているものをキャッシュするのは良い考えではないでしょうか？

それらは変更されていないので、速度が重要な場合は、テーブルを生成してルックアップを実行します。

于 2011-01-22T15:50:23.233 に答える
0

fibonacciRecursiveへの呼び出しの総数が、返される最終値と正確に等しいことを簡単に確認できます（帰納法で証明できます）。それは確かに入力数で指数関数的です。

于 2011-01-22T15:54:45.833 に答える