0

現在のマシンでn番目のフィボナッチ数を計算するのにどれくらいの時間が必要かを知る方法は何ですか？たとえば、現在のマシンでは、30番目の要素は67ミリ秒で計算され、40番目の要素は554ミリ秒で計算されます。99番目の要素の時間を計算する方法は？

int fib(int n)
{
    if( n <= 2) 
        return 1
    else
        return fib(n-1) + fib(n-2)
}

アップデート

フィボナッチN番目とms（現在のPCがn番目のフィボナッチ要素を計算するのにかかった時間、ミリ秒単位の時間） http://pastebin.com/PGnd54Hq

Matlab：コード http://pastebin.com/L9CH53Pf

グラフ

N番目の要素の時間を見つける方法は？

4

5 に答える 5

2

ある範囲の値の時間を測定し、テーブルを作成します。

n | time

次に、を使用して指数関数matlabに適合させます。

big-O表記は漸近的であり、多数の要素に当てはまることに注意してください。

ここに画像の説明を入力してください

そのためのACコードを書いてみてください。フィボナッチルーチンのインライン関数を使用して、ctimeを使用する時間を取得し、値を2つの配列に格納します。その後、matlabまたは`pythonを使用して結果を分析します。

結果を投稿してください...

于 2012-10-11T16:22:03.160 に答える
2

関数への再帰呼び出しの数もフィボナッチ数列に従っていることを証明するのは簡単です。同様に、F0=0とF1=1が基本ケースである場合F2、関数への2回の呼び出しF3が必要であり、3回の呼び出しが必要になります。

これは、@0x90が提案したようにあなたの時間に合うように指数関数を使用することを正当化します。

于 2012-10-11T16:27:32.463 に答える
2

どうやらあなたはフィボナッチ数列を計算するための素朴なアルゴリズムの実装を実行しています。このアルゴリズムには指数関数的な複雑 さがあります。フィボナッチ数列の計算の複雑さ（〜）。したがって、コンピュータでのプログラムの実行時間は約です。1つの関数の結果（プログラムの実行時間）がわかれば、定数を計算して、さまざまなの近似時間を計算できるはずです。θ(1.6n)k*1.6nnkn

于 2012-10-11T16:29:34.867 に答える
1

パフォーマンスは、関数呼び出しの数と各呼び出し内の計算の数だけでなく、再帰的アルゴリズムによってスタックをさらにプッシュするために支払う金額（時間的に）によっても決まります。そのスタックプッシュがどのように機能するかはわかりませんが、特定のしきい値を超えると、より急速に増加し始める可能性があります。したがって、このしきい値がどこで開始され、（指数関数的にまたは何でも）上下両方に適合するかを確認する必要があります（再帰スタックを構築し始めると、より類似したパフォーマンスペナルティが発生する可能性があります）。

明らかに、それは問題ではありませんが、数学的に洗練されており、最も単純なコードが必要な場合でも、フィボナッチ数を再帰的に計算するべきではありません。

[追加/編集]時間測定のグラフを追加したことに気づきました。より良い洞察を得るために、対数目盛を垂直方向（時間）に使用することをお勧めします。これにより、グラフ全体が「純粋に」指数関数であるか（対数プロット上の直線）、またはそれが（異なる）指数関数のシーケンスであるか、それとも他の何かであるかがより明確に示されます。おそらく、指数部分は「どこか」で始まるか、別の指数に変化します。

于 2012-10-11T22:10:03.460 に答える
0

リストされたコードから、各呼び出しは2つの呼び出しを行います。したがって、この質問に対する簡単な答えは、呼び出しの数がnごとに2倍になるため、呼び出しの数は2 ^（n-1）になるということです。たとえば、fib（10）を計算している場合、呼び出しの数は2 ^ 9 = 512になります。したがって、1つを作成するのに1秒かかった場合、fib（10）のすべての呼び出しを行うのに512秒かかります。 ）。

于 2012-10-11T20:52:05.387 に答える