アルゴリズム

皆dankogaiが大好きだね.

O記法の定義

O(f(n))={g(n) | ある定数Nと定数cが存在して $n\geq N$ ならば $g(n)\leq c f(n)$ }.
$\phi=(1+\sqrt{5})/2$ として $O(\phi^n)\subseteq O(2^n)$ なのでナイーブな実装の関数呼び出し回数をO(2^n)と言うのは間違いではない. 漸近的にしか評価してないんだから.
これは某コメントに向けて

O記法を何を評価するために使っているか

関数の呼び出し回数. (向こうのコメント欄に全体の計算量と誤解している人が居る.)
TM的な定義では足し算や掛け算にも時間が掛かるので計算時間のオーダーも増える.

その他

を計算するのには繰り返し二乗法で掛け算を高々2log(n)回. ただ実数計算はしたくないのでとおいてa_n, b_nを計算した方が良い.
- See also http://d.hatena.ne.jp/inamori/20071129/p1
- 更には行列演算を使った方が良い (参照:コメント欄及びkeyword:フィボナッチ数列).
- $\left(\begin{array}{cc}1&1\\1&0\\ \end{array}\right)^n$ とか.
O()という書き方は誤解を招くよね.
知っている人は自動補完されるからいいけど, 知らない人に教える記事として読むと定義と正確性に問題があるよね.
~~あとメモ化のときの最初の呼び出し回数の評価も間違ってるよね. 1回目は関数をナイーブな実装で評価するから.~~
- 404 Blog Not Found:私ごときがアルゴリズム本を書くことにした訳. 「ツッコミ」が間違ってました. 確かにO(n)っす. 申し訳ない (本当に無い).

補遺

影響力がありそうな方の次のエントリ2つを見て，

アルゴリズムについてこうなんというか不正確な記述がたくさんあって，書いている本人が理解してるかどうかも判断しにくい文章にたくさんブックマークがついていて，しかもそのような方がアルゴリズムに関する書籍を執筆しようとしているという状況がなんかこわいです．

岡本先生頑張って下さい(w