フィボナッチのさまざまな実装のBig-O

Question

フィボナッチシーケンスのn番目の項を計算できるさまざまな手段でコードを実装しようとしましたが、私が学んだことを検証したいと考えています。

次のように反復的な実装は次のとおりです。

public int iterativeFibonacci(int n) 
{ 
    if (n == 1) return 0; 
    else if (n == 2) return 1; 
    int i = 0, j = 1, sum = 0; 
    for (; (n-2) != 0; --n) 
    { 
    sum = i + j; 
    i = j; 
    j = sum; 
    } 
    return sum; 
} 

次のように再帰的な実装は次のとおりです。 -

public int recursiveFibonacci(int n) 
    { 
    if (n == 1) return 0; 
    else if (n == 2) return 1; 
    return recursiveFibonacci(n-1) + recursiveFibonacci(n-2); 
    } 

次のようにメモ化の実装は次のとおりです。 -

public int memoizedFibonacci(int n) 
    { 
    if (n <= 0) return -1; 
    else if (n == 1) return 0; 
    else if (n == 2) return 1; 
    if (memory[n-1] == 0) 
     memory[n-1] = memoizedFibonacci(n-1); 
    if (memory[n-2] == 0) 
     memory[n-2] = memoizedFibonacci(n-2); 
    return memory[n-1]+memory[n-2]; 
    } 

私は」これらの実装のBig-Oを理解しようとすると疑いがあります。私は反復実装がO（n）であると信じています.N-2回ループします。

再帰関数では、値が再計算されているため、O（n^2）だと思います。

memoized関数では、memoizationに基づいて値の半分以上がアクセスされます。私はそれを読んだ問題のスペースを減らすために一定の時間がかかる場合、とそのアルゴリズムはO（ログN）です。一定量。メモの実装がO（n）という複雑さを抱いていると思いますか？もしそうなら、3つすべての中で反復的な実装が最善ではないでしょうか？ （memoizationが必要とする追加のメモリを使用しないため）。

Answer 1

再帰型は多項式時間ではありません。指数関数的です。tightly bounded at φⁿここで、φは黄金比（≒1.618034）です。再帰的なバージョンは（n）のメモリを使用します（スタックは使用されます）。各数値は一度だけ計算されるので

メモ化バージョンは、最初の実行時にO（N）時間がかかります。ただし、現在の実装では、（n）のメモリを使用します（nは計算値の格納から、また最初の実行時のスタックからのものです）。あなたはそれを何度も実行する場合は、時間複雑になるだろうMは、すべての入力のnとQの最大であるO（M + Q）は、クエリの数です。メモリの複雑さは、O（M）になります。これは、すべての計算値を保持する配列に由来します。

使用すると、1つの実行を検討している場合、それはまた、（N）Oで実行されますが、メモリのO（1）を計算するために、一定量を使用して反復的な実装は、最高です。実行回数が多い場合は、すべてを再計算するため、パフォーマンスはメモのバージョンほど良くない可能性があります。

（ただし、実際には、パフォーマンスとメモリの問題が発生するずっと前に、64ビット整数でも数値がオーバーフローする可能性が高いため、正確な分析では計算する場合に加算にかかる時間を考慮する必要があります完全な数字）。上述plesivとして

、フィボナッチ数は、（各ステップで指数を半分にすることにより、同じトリックとして高速べき乗を使用して）行列乗算によって（Nログ）Oに計算することができます。