だから、私はフィボナッチ数を得るためにJavaで再帰的な方法を持っています - 私が持っている唯一の質問は、時間の複雑さは何ですか？私はそれがO（2^n）だと思うが、間違いかもしれない？ （繰り返しが良いとわかりますが、それはエクササイズです）フィボナッチアルゴリズムの時間複雑度
public int fibonacciRecursive(int n)
{
if(n == 1 || n == 2) return 1;
else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
}
再帰コードには指数ランタイムがあります。しかし、私はベースが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
これはフィボナッチ数自身の再帰的定義に非常によく似ています。再帰方程式の+1は、おそらく大きなnに対しては無関係です。私はそれが線維数とほぼ同じくらい速く成長すると信じています。それらは基底として黄金比で指数関数的に成長します。
メモ処理、つまり既に計算された結果をキャッシュすることでスピードアップできます。それからそれは反復バージョンのようなO（n）ランタイムを持っています。
あなたの反復コードはO（N）のランタイム
あなたはO（n）のステップと、各反復のために一定の時間を持つ単純なループを持っています。
ああ、申し訳ありませんが、間違ったコードを投稿しました。私は再帰的なものが必要でした！私の悪い、秒で編集されます。 – Koeneuze
O（^ * n *）= O（2^* n *）。 –
@larsだから私は「もちろんO（1.62）は自動的にO（2）である」と書きました。しかし、2^nよりも近い上限を知ることはまだ興味深いです。 – CodesInChaos
O（2^n）？私はここでO（n）しか見ることができません。
なぜこれらの計算と再計算を続けるのだろうと思いますか？メモリ要件があまりにも厄介にならない限り、あなたが良いアイデアであるものをキャッシュしないでしょうか？
変更されていないので、速度が重要であればテーブルを生成してルックアップを行います。
fibonacciRecursiveへの呼び出しの総数が返された最終値と正確に等しいことは容易にわかります（誘導によって証明すること）。それは実際に入力番号で指数関数的です。
いいえ少し上です。例えば、Fibo（2）は3つの呼び出しを持ちますが、2を返します。しかし、大きなnの場合、その違いはあまり重要ではありません。 – CodesInChaos
各関数呼び出しは、1つの加算だけを返します。または、1を返します。基本ケースは値1を返します。したがって、加算の総数はfib（n）-1です。したがって、関数呼び出しの総数は2 * fib（n）-1であるため、時間複雑度はO（2^N）で囲まれたΘ（fib（N））=Θ（phi^N）です。
あなたはOでのFn（n個のログを記録）
は「反復がずっといいです」を計算するために、この
を使用することができ、一般的に間違っています。あなたの素朴な再帰的な実装に勝つのは事実ですが、その実装は、動的プログラミングを使った反復実装と本質的に同じように改善することができます。 –