回答編集履歴
1
追記
answer
CHANGED
|
@@ -17,4 +17,16 @@
|
|
|
17
17
|
|積み上げ式|O( n )|メモ化（KSwordOfHasteさんの回答）|
|
|
18
18
|
|行列計算|O( log n )|行列を使う方法|
|
|
19
19
|
|
|
20
|
-
定義通り、積み上げ式はわかりました。行列計算を調べてみましょう。
|
|
20
|
+
定義通り、積み上げ式はわかりました。行列計算を調べてみましょう。
|
|
21
|
+
|
|
22
|
+
|
|
23
|
+
**補足**
|
|
24
|
+
|
|
25
|
+
フィボナッチ数の一般項は、もとはオイラーが発見したそうです。（証明は難しいです）
|
|
26
|
+
F(n) = (Φ^n - (1-Φ)^n)/sqrt(5) ただし Φ = (1+sqrt(5))/2
|
|
27
|
+
|
|
28
|
+
一般項の近似式は次のようになります。計算量を考えるとしたらこれでいいと思います。
|
|
29
|
+
F(n) ≒ Φ^n/sqrt(5) 第二項(1-Φ)^n/sqrt(5)の絶対値は、最大で0.447..なので省略
|
|
30
|
+
|
|
31
|
+
第二項の性質を使って一般項を求め直すと次のようになります。これは一種のトリックです。
|
|
32
|
+
F(n) = floor((1/5)*Φ^n + (1/2)) floor はガウス関数。ただし正のフィボナッチ数のみ。
|