フィボナッチ数列の計算量
https://stackoverflow.com/questions/360748
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
Big-O 表記法は理解できますが、多くの関数の計算方法がわかりません。特に、私はフィボナッチ数列の単純バージョンの計算の複雑さを理解しようと努めてきました。
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
フィボナッチ数列の計算量はどのくらいですか?また、どのように計算されますか?
解決
計算する時間関数をモデル化します。 Fib(n) 計算にかかる時間の合計として Fib(n-1) 計算にかかる時間もプラス Fib(n-2) それらを合計する時間に加えて (O(1)）。これは、同じ評価が繰り返されることを前提としています。 Fib(n) 同じ時間かかります - つまりメモ化は使用されません。
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
この漸化関係を (たとえば、生成関数を使用して) 解くと、最終的に答えが得られます。
あるいは、深さのある再帰ツリーを描画することもできます。 n そして、この関数が漸近的であることを直感的に理解します。 O(2n). 。その後、帰納法によって推測を証明できます。
ベース： n = 1 明らかです
仮定する T(n-1) = O(2n-1), したがって
T(n) = T(n-1) + T(n-2) + O(1) に等しい
T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)
ただし、コメントに記載されているように、これは厳密な制限ではありません。この関数に関する興味深い事実は、T(n) が漸近的に 同じ の値として Fib(n) どちらも次のように定義されているため、
f(n) = f(n-1) + f(n-2).
再帰ツリーのリーフは常に 1 を返します。の値 Fib(n) 再帰ツリー内のリーフによって返されるすべての値の合計であり、リーフの数と等しくなります。各リーフの計算には O(1) かかるため、 T(n) に等しい Fib(n) x O(1). 。したがって、この関数の厳密な境界はフィボナッチ数列自体 (~θ(1.6n)）。上で述べたように生成関数を使用すると、この厳密な境界を見つけることができます。
他のヒント
ただ、完了するまでにF(n)のために実行する必要がどのように多くの文を自問します。
F(1)について、答えが1（条件の最初の部分）である。
F(n)について、答えはF(n-1) + F(n-2)です。
それでは、機能、これらの規則を満たしますか？試す N （A> 1）
N == （N-1） + （N-2）
でスルー除算（N-2）：
A 2 == A + 1
aのために解決し、それ以外の場合は黄金比のとして知られているあなたは、(1+sqrt(5))/2 = 1.6180339887を取得します。
だから、指数関数時間がかかります。
その結果、あなたはフィボナッチ数列の非常に近い近似値に直接スキップすることができます：
Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)
と言うので、ナイーブアルゴリズムの最悪のパフォーマンスであること
O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))
PS：N番目のフィボナッチ数の閉形式の議論がありますする以上ウィキペディアであなたはより多くの情報が欲しい場合ます。
私はpgaurに同意し、rickerbh、再帰フィボナッチの複雑さはO（2 ^ n）がある。
私はむしろ単純化することにより、同じ結論に達しましたが、私はまだ有効な推論を信じています。
まず、それはすべての（今からF（））何回再帰フィボナッチ機能を考え出すことだN番目のフィボナッチ数を計算するときに呼び出されます。それはnに一度シーケンス0で番号ごとに呼び出される場合は、それが各数のためにn倍呼び出された場合、その後、我々は、O（n）を持って、我々は、O（N * N）、またはO（N ^ 2）を取得します等々ます。
そこで、F（）が数nに対して呼び出されたとき、回数がF（）0との間に所定の数のために呼び出され、N-1は、我々は0に近づくにつれて大きくなる。
第一印象としては、我々があれば、それは（ピラミッド形状の並べ替えを濡れ私たちは与えられた数のために呼び出されたときF（）あたりのユニットを描く、視覚的な方法でそれを置く場合ように私には思えます水平方向中央部）。このような何かます：
n *
n-1 **
n-2 ****
...
2 ***********
1 ******************
0 ***************************
さて、質問は、nが大きくなるにつれて拡大し、このピラミッドのベースは、どのくらいの速ですか？
のは、例えば、Fを実際のケースを見てみましょう（6）
F(6) * <-- only once
F(5) * <-- only once too
F(4) **
F(3) ****
F(2) ********
F(1) **************** <-- 16
F(0) ******************************** <-- 32
我々は、このサンプルの場合について2である2 ^ 5、である、F（0）が32回呼び出さ参照^（N-1）
は、今、私たちは、F（x）は、すべてで呼び出される回数を知りたい、と私たちは、F（0）と呼ばれていることの一部でしかないの回数を見ることができます。
我々は精神的にFへ（2）ライン（1）の線Fに（6）Fから全て*のを移動した場合、、我々は、F（1）、F（0）株は現在、長さが同じであることがわかり。これ意味する、総時間F（）が呼び出されたとき、N = 6 2x32 = 64 = 2 ^ 6であります。
さて、複雑さの点でます：
O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
あなたはそれを拡張し、可視化を持つことができます。
T(n) = T(n-1) + T(n-2) <
T(n-1) + T(n-1)
= 2*T(n-1)
= 2*2*T(n-2)
= 2*2*2*T(n-3)
....
= 2^i*T(n-i)
...
==> O(2^n)
これは、2 ^ n個（他のコメントで述べたように）によって2^(n/2)によって下端に上端に制限されます。そして、その再帰的な実装の興味深い事実は、それがのFib（n）は自身の下限タイト漸近を持っていることです。これらの事実は、まとめることができます：
T(n) = Ω(2^(n/2)) (lower bound)
T(n) = O(2^n) (upper bound)
T(n) = Θ(Fib(n)) (tight bound)
その
証明の答えは優れていますが、本当に自分を納得させるには、常に手動で数回反復する必要があります。そこで私はホワイトボードに小さなコーリングツリーを描き、ノードの数を数え始めました。カウントを合計ノード、リーフ ノード、内部ノードに分割しました。私が得たものは次のとおりです。
IN | OUT | TOT | LEAF | INT
1 | 1 | 1 | 1 | 0
2 | 1 | 1 | 1 | 0
3 | 2 | 3 | 2 | 1
4 | 3 | 5 | 3 | 2
5 | 5 | 9 | 5 | 4
6 | 8 | 15 | 8 | 7
7 | 13 | 25 | 13 | 12
8 | 21 | 41 | 21 | 20
9 | 34 | 67 | 34 | 33
10 | 55 | 109 | 55 | 54
すぐに気になるのは、リーフ ノードの数が fib(n). 。さらに数回繰り返して気づいたのは、内部ノードの数が fib(n) - 1. 。したがって、ノードの総数は次のようになります。 2 * fib(n) - 1.
計算の複雑さを分類するときに係数を省略するため、最終的な答えは次のようになります。 θ(fib(n)).
再帰アルゴリズムの時間複雑性は良好再帰ツリーを描くことによって推定することができ、この場合、再帰ツリーを描画するための漸化式は、T（N）= T（N-1）+ T（N-2）+ O（1あろう） 各ステップは、それが中にnの値をチェックするだけで1つの比較を行うために、（1）一定の時間を意味するOを取ることに注意してのの場合のblock.Recursionツリーは
のようになります。 n
(n-1) (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on
ここで上記ツリーの各レベルは、iで示され、言うことができます したがって、
i
0 n
1 (n-1) (n-2)
2 (n-2) (n-3) (n-3) (n-4)
3 (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)
I、ツリー末端の特定の値に言う木の高さがn-1であることを意味する場合、N-I = 1、従って、I = N-1、その場合は次のようになります。 今再発に関して述べたように、各ステップは、O（1）時間がかかるというtree.Noteにおけるn層の各々について行われるどのくらいの仕事を参照できます。
2^0=1 n
2^1=2 (n-1) (n-2)
2^2=4 (n-2) (n-3) (n-3) (n-4)
2^3=8 (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6) ..so on
2^i for ith level
以来、I = N-1となる各レベルで行わツリーワークの高さ
i work
1 2^1
2 2^2
3 2^3..so on
各レベルで行われる作業の和であろう行わ従って全仕事は、それゆえ、それはなります2 ^ 0 + 2 ^ 1 + 2 ^ 2 ^ 3 + 2 ... + 2 ^（N-1）ので、I = N -1。 等比級数によってこの合計が2 ^ nは、ここではそのための総時間複雑さの O（2 ^ N）の
まあ、それは唯一の再帰は、かなりの時間（分割統治）を取っているこの機能のようにO(2^n)されるように私に従っ。我々はF(n-(n-1))すなわちF(1)レベルに達したときに葉がアプローチされるまで、上記の関数がツリーに継続する、ことを参照してください。私たちは、ツリーの各深さで遭遇した時の複雑さを書き留めるときに、ここでは、加算シリーズは、次のとおりです。
1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1
それは2^n [ O(2^n) ]の順である。
http://www.ics.uci.edu/~eppstein /161/960109.htmlする
の時間（N）= 3F（N） - 2 の
フィボナッチの単純な再帰バージョンは、計算の繰り返しにより設計上指数関数的になります。
ルートでは以下を計算しています。
F(n) は F(n-1) と F(n-2) に依存します
F(n-1) は再び F(n-2) と F(n-3) に依存します。
F(n-2) は再び F(n-3) と F(n-4) に依存します。
各レベル 2 で再帰呼び出しが行われ、計算で大量のデータが無駄になる場合、時間関数は次のようになります。
T(n) = T(n-1) + T(n-2) + C、C は定数
T(n-1) = T(n-2) + T(n-3) > T(n-2) の場合
T(n) > 2*T(n-2)
...
T(n) > 2^(n/2) * T(1) = O(2^(n/2))
これは分析の目的には十分な下限にすぎませんが、リアルタイム関数は同じフィボナッチ数式による定数の因数であり、 閉じた形式 は黄金比の指数関数であることが知られています。
さらに、次のような動的プログラミングを使用して、フィボナッチの最適化されたバージョンを見つけることができます。
static int fib(int n)
{
/* memory */
int f[] = new int[n+1];
int i;
/* Init */
f[0] = 0;
f[1] = 1;
/* Fill */
for (i = 2; i <= n; i++)
{
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
それは最適化され、実行するだけです n ステップですが、指数関数的でもあります。
コスト関数は、入力サイズから問題を解決するためのステップ数まで定義されます。フィボナッチの動的バージョンを表示すると (n テーブルを計算する手順)、または数値が素数かどうかを知るための最も簡単なアルゴリズム (sqrt(n) 数値の有効な約数を分析します)。これらのアルゴリズムは の上） または O(sqrt(n)) しかし、これは次の理由から単純に真実ではありません。アルゴリズムへの入力は数値です。 n, 、バイナリ表記を使用した整数の入力サイズ n は log2(n) 次に変数の変更を行います
m = log2(n) // your real input size
入力サイズの関数としてステップ数を調べてみましょう
m = log2(n)
2^m = 2^log2(n) = n
この場合、入力サイズの関数としてのアルゴリズムのコストは次のようになります。
T(m) = n steps = 2^m steps
これがコストが指数関数的に増加する理由です。
