1

実装しようとしているアルゴリズムがあります。最悪の場合の実行時間を表す関数を決定するように依頼されました。入力として、それはある長さの配列を取ります（それをnと呼びましょう）。次に、それが行うことは次のとおりです。

if (n==0){ return 0;}
else if(n==1){return A[0];}
else{
     return f(n-1)+f(n-2)
}

実装の詳細が少しまばらである場合は申し訳ありませんが、ある意味では、fibbanociシーケンスのようなものにかなり似ています。このアルゴリズムの最悪の場合の実行時間はt（n）= 2 ^ nだと思います。これは、nが大きい場合、2つの別々の計算に分解され、さらに2つに分割されるためです。これを正式に正当化する方法がわかりません

4

1 に答える 1

5

まず、実行時間の再帰を取得しましょう。

T(0) = T(1) = 1

どちらも数値を返すだけなので（1つは配列ルックアップですが、それも一定時間です）。そしてn > 1私達は

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

2つの結果を評価f(n-1)しf(n-2)て追加するためです。これは、フィボナッチ数列自体とほぼ同じ再発F(n) = F(n-1) + F(n-2)であり、結果は密接に関連しています。

 n | T(n) | F(n)
----------------
 0 |   1  |   0
 1 |   1  |   1
 2 |   3  |   1
 3 |   5  |   2
 4 |   9  |   3
 5 |  15  |   5
 6 |  25  |   8
 7 |  41  |  13
 8 |  67  |  21
 9 | 109  |  34
10 | 177  |  55
11 | 287  |  89

値を見ると、

T(n) = F(n+2) + F(n-1) - 1

必要に応じて、誘導でそれを証明できます。

フィボナッチ数列の項は、で与えられるF(n) = (φ^n - (1-φ)^n)/√5ので、ここで、フィボナッチ数列の複雑さのように、の複雑さもφ = (1 + √5)/2であることがわかります。これは、よりも優れていますが、それでも指数関数的であるため、この方法を使用した計算は、小さい場合にのみ実行可能です。fΘ(φ^n)Θ(2^n)n

于 2012-09-29T19:46:42.720 に答える