フィボナッチ数列のn番目の項を計算するための最速のJavaアルゴリズムですか？

Question

フィボナッチシーケンスのn番目の項を計算するための最も速いJavaアルゴリズムは何ですか。

these algorithmsが見つかりました。反復アルゴリズムは再帰アルゴリズムと解析アルゴリズムよりも速くなければならないと思います。

Answer 1

十分に大きな数のフィボナッチ数をすべて事前に計算し、これらの数値を保持できるタイプの数値を持つ配列を定義するソースコードスニペットを生成します。

次に、配列内のインデックスnの値を取得できます。これはO(1)です。それよりはるかに早く来ない。

Answer 2

Try dynamic programming n-1番目のフィボナッチ数のすべての値を保持する配列を作成します。最初に実行すると、通常のフィボナッチ関数と同じくらい時間がかかりますが、配列内の値をすでに持っているので、その後の呼び出しはO（1）で実行できます。

Answer 3

私の経験では、分析バージョンは通常、実際には非常に高速ですが、Rosettaコードノートでは、シーケンスの第92番まで正確です。

再帰的なバージョンの実行には指数関数的な時間がかかりますので、中程度のサイズの場合でも非常に遅くなる場合がありますn反復関数と末尾再帰関数は、nで時間が直線的になります。フィボナッチ配列のmatrix formからより速いO（lg n）時間アルゴリズムを導くことができる。

再帰アルゴリズムとテール再帰アルゴリズムの説明については、SICPを参照してください。

Answer 4

答えは、いつものように「それは依存している」。一般的には、フィボナッチ数が急激に増加する傾向があるため、実際にはリンクのアナリティクスセクションが指摘するように指数関数的に多くのフィボナッチ数を格納することはできません。

ほとんどの実用的な目的のために、答えは「計算しない - キャッシュ」です。つまり、ルックアップテーブルを使用します。

従来の記憶方式では、O（d^2）のように再帰的に計算するよりはるかにうまく行かないでしょう。 dは出力の桁数であり、より複雑な任意のサイズの数値演算が競合するのは困難です。

"Analytic"は、ベースが不便で、高速整数計算を捨ててしまうので、おそらく低速メソッドの1つです。

Answer 5

特にJavaでこれをターゲットにしていましたが、私は昨夜のPython 3でこれをさまざまな方法で実装していました。特に、素朴な再帰的な実装と分析的な実装（私はそれを閉形式と呼んでいます）を見ました。ここでは、コードされ、sansそれのための私のユニットテスト：ここで

import math 
from timeit import Timer 

def fib_recursive(n): 
    """ 
     Compute the Fibonacci sequence from a given number n 
    """ 
    if n < 2: 
     return n 
    else: 
     return fib_recursive(n - 2) + fib_recursive(n - 1) 

def fib_closed_form(n): 
    """ 
     Compute the Fibonacci sequence using a closed form. 
    """ 
    def calc_golden_ratio(): 
     return (1 + math.sqrt(5))/2 

    gr = calc_golden_ratio() 
    inverse_gr = 1 - gr 
    numerator = math.pow(gr, n) - math.pow(inverse_gr, n) 
    return numerator // math.sqrt(5) 

if __name__ == '__main__': 
    for n in range(0, 10): 
     n = str(n) 
     time = Timer("fib_closed_form(" + n + ")", "from __main__ import fib_closed_form") 
     print('Fib_Closed_Form(' + n +') = ' + str(time.timeit())) 
     time = Timer("fib_recursive(" + n + ")", "from __main__ import fib_recursive") 
     print('Fib_Recursive(' + n +') = ' + str(time.timeit())) 

1-10からバリューのホテル（時間は秒単位であり、timeitモジュールを使用して測定）を用いてこれらの機能のタイミングです。

Python 3.2.2 (default, Nov 21 2011, 16:50:59) 
[GCC 4.6.2] on staggerlee, Standard 
>>> 
Fib_Closed_Form(1) = 5.808775901794434 
Fib_Recursive(1) = 0.6938691139221191 

Fib_Closed_Form(2) = 6.142783880233765 
Fib_Recursive(2) = 1.9276459217071533 

Fib_Closed_Form(3) = 6.62189793586731 
Fib_Recursive(3) = 3.6403379440307617 

Fib_Closed_Form(4) = 6.376585960388184 
Fib_Recursive(4) = 6.733421802520752 

Fib_Closed_Form(5) = 6.566863059997559 
Fib_Recursive(5) = 11.409136056900024 

Fib_Closed_Form(6) = 6.521269083023071 
Fib_Recursive(6) = 18.514809131622314 

... 

Fib_Closed_Form(10) = 6.631903886795044 
Fib_Recursive(10) = 131.51839208602905 

あなたが見ることができるように、この閉じた形は、より高いアップを持っている：それは合計ですべてのコールにかかる時間の結果であるように、各コールは、デフォルトではtimeitモジュールで1000000回行われますフロントコスト。再帰的な人はそれを水から吹き飛ばします！しかし、競争力はn = 4の値でしか維持されません。あなたはそれが悪化するタイミングとなっているのを見ることができます。 6になるまでには、これは正しい方向ではないことがすでにわかります。

ところで、私は最後の夜にn = 25を試みました。閉鎖されたフォームにはほぼ同じ時間がかかり、再帰的なフォームは私が寝る前に終了しませんでした（少なくとも30分実行中）。

私の主なポイントは、これは実装が簡単であることと、いくつかの単体テストを思いつくことは簡単です。 Javaのような言語でタイミングをとることは、追加設定なしでは複雑になる可能性がありますが、Javaでその結果を見ることができます。