アルゴリズム百選 - フィボナッチ数列にO()を学ぶ
弾さんの記事。
- フィボナッチ数列の一般項を求める式を使ったときってO(1)って言えるのだろうか？
- 「O()が小さいからといって速いとは限らない」が抜けている。
読んでいるうちにアルゴリズムの本が書きたくなってきたりして。
追記(1)：
弾さんの追加記事。
弾さんのO記法の定義がわかりません。奥村先生の『C言語による最新アルゴリズム事典』の「O記法」には以下のように書かれています。
もっと正確にいえば，定数c(> 0)，Nが存在して，n≧Nならば必ず|f(n)|≦c|g(n)|が成り立つとき，“n→∞のときf(n)＝O(g(n))である”という．
この定義だと、フィボナッチ数列の一般項を求める式を使ってもO(1)にはならないと思います。
参考：
追記(2)：
弾さんの追加記事。
うーん、ブログで公開しているのは「いくらでも突っ込んで」という主旨だと思ったのですが、違うのかな。O記法に厳密な定義がある以上、それで突っ込むのは正当な話だと思うんですが（カジュアルに書くのに反対しているわけではありません）。本は読者を選べませんから、そういう突っ込みが来るのは避けられない。
とはいえ、pedantic な部分がまるで不要かというとそうでもありません。そのあたりの落としどころが難しいところですし、私もまだどこまで pedantic に、あるいはどこまで「いいかげん」に書くかは決めあぐねています。
404 Blog Not Found:アルゴリズム百選 - 用語の定義、またはその欠如
その落としどころこそが本の命であり、著者の腕の見せ所だと思います。弾さん、がんばってください。
それはさておき…何だかアルゴリズム本は楽しそうだなあ。ブクマでのエール感謝します。すごく心が動きますね(^_^;（現在結城が書いているのはアルゴリズム本ではありませんけれど）。
追記(3)：
なるほど。オーダー記法の定義だけでははっきりしたことになりませんね。理解しました。
O(1)とするかO(n)とするかは計算モデルに依存します．
2007-12-06
(略)
計算モデルによってはO(1)なのかもしれません.
