2

この関数の T(n) を計算しようとしていますが、思いついたのは T(n) = T(n) + T(n) + O(1) です。関数 g() への 2 回の再帰呼び出しに対して 2 つの T(n) があり、次に加算などのすべての一定時間操作に対して O(1) があります。私の数学のバックグラウンドはあまり健全ではありません。

int g(int y) {
 if (y <= 0) {
  return 1;
 }
 else {
  return g(y - 1) + g(y - 2);
 }
}
4

2 に答える 2

11

フィボナッチ数を計算する時間の複雑さは、使用するアルゴリズムによって異なります。それらを計算するためのアルゴリズムが少なくとも 4 つあります (時間の複雑さが異なります)。

O( \φ ^n)

最初に、再帰的なフィボナッチ関数の呼び出しグラフを見て、これを理解できることを述べます。

コールグラフは実際にはツリーです。

ここに画像の説明を入力

このツリーがいくつのノードを持っているかを調べることにすべてを還元できます。

F(n) のコール グラフのノード数は、ルートと F(n-1) のコール グラフのノード数 + F(n-2) のコール グラフのノード数を持ちます。

F(n) のノード数を L(n) で表します (文字 L は偶然ではないことがわかります)。

上で説明したように、L(n) = L(n-1) + L(n-2) + 1 です。

しかし、待ってください。これらは正確に レオナルド数であり、一般的な閉形式を持っていることがわかります。

ここに画像の説明を入力

( "a(n) is the number of nodes in the Fibonacci tree of order n." A001595 )

の上）

複雑さ O(n) のメモ化を含む別のアルゴリズムがあります(ここに例と別のものがあります)。これには、T(n) の結果をベクトルに格納し、必要な n まで n=1 について T(n) を徐々に計算することが含まれます。

本当に正確にしたい場合は、これも O(n) ではありません。加算の数のコストは O(1) であると想定されているためです。ただし、F(n) が大きくなるにつれて、加算のコストは2 つのフィボナッチ数は O(n) です。詳細については、こちらをご覧ください。したがって、この実装の実際の複雑さは O(n^2) です。

O(1)

任意精度の算術演算またはスマートな丸めを使用することを考えると、複雑さ O(1) の別のアルゴリズムもあります。ビネーの公式からきています。Binet の公式の証明については、13 ページのセクション 1.3 を参照してください。生成関数を使用するか、行列の固有分解を見つけて、それを使用して n 乗を計算できます。これを行うと、閉じた形式の数式が n 乗行列のセルの 1 つになります。

本当に正確にしたい場合は、実際には O(log(n))です。これは、Binet の式を計算するために使用する2 乗による累乗(反復 2 乗、2 乗累乗アルゴリズム、または 2 乗累乗とも呼ばれます) であるためです。

通常、 の累乗は O(1) であると仮定しますx^nが、そうではなく、乗算の数で O(log(n)) です。正確に言うと、使用する乗算アルゴリズムに依存する乗算の​​コストを考慮に入れる必要があります。

Binetの式は次のとおりです。

ここに画像の説明を入力

フィボナッチ数列が行列形式でどのように見えるかを次に示します。

ここに画像の説明を入力

二乗によるべき乗は次のとおりです。

ここに画像の説明を入力

更新 2015-06-29 :

O(ログ(n))

O(log(n)) でフィボナッチ数を計算する別の方法があります。2 つの ID が使用されています

これらは、 F(n)、F(n+1)に基づくF(2 * n+1)および F (n-1)、F(n)、F(n )に基づくF(2*n)の計算を可能にします。+1) . このアルゴリズムは、nの最上位ビットを検出し、最下位ビットまで繰り返しながら、途中で恒等式を使用してフィボナッチ数を計算します。ここにアルゴリズムの実装があります。2 つの恒等式は、(前のリンクのように)二次体 ℚ(√5) で導出するか、上記の行列の n 乗と 2n 乗から導出することができます (セクション 2.5「Matrix Methods」を参照)。 」の23 ページJL Hollowayによる「フィボナッチ数をすばやく計算するためのアルゴリズム」 )。

于 2013-03-21T21:04:50.310 に答える
0

再帰関係は次のとおりです。

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

方程式に T(n/b) の形式の項がないため、これはマスター定理のどのケースにも当てはまりません。

したがって、少し奇妙なアプローチを取る必要があります。

上記の定義により、T(n-1) は T(n-3) + T(n-2) + O(1) に等しいため、T(n) は次のように記述できます。

T(n) = 2T(n-2) + T(n-3) + 2*O(1)

T(n-2) = T(n-3) + T(n-4) + O(1) なので、T(n) を次のようにさらに単純化できます。

T(n) = 3T(n-3) + 2T(n-4) + 3*O(1)

ここまでで、パターンが見え始めているはずですが、適切な測定のために、さらに一歩進めてみましょう。T(n-3) = T(n-4) + T(n-5) + O(1) であるため:

T(n) = 5T(n-4) + 3T(n-5) + 4*O(1)

第 1 項の係数は、フィボナッチ数列のパターンに従います。次のラウンドでは、8T(n-5) が主項になります。次のラウンドでは 5T(n-6) になるため、第 2 項もフィボナッチ数列に従います。第 3 項は、n と同じように成長しています。

したがって、T(1) は単なる O(1) であるため、次のようになります。

T(n) = x*O(1) + y*O(1) + n*O(1) ここで、x はフィボナッチ数列の n 番目の項、y はフィボナッチ数列の (n-1) 番目の項です。 .

先頭の用語を見ると、ビッグオー分析は、基本的に、n に基づいて x を計算するための数式であることがわかります。

ここでその式を見ることができます: http://www.askamathematician.com/2011/04/q-is-there-a-formula-to-find-the-nth-term-in-the-fibonacci-sequence/

big-O 分析を適用すると、これはすべて次のように要約されます: O(1.6^n)

于 2013-03-21T21:32:45.727 に答える