チューリング賞モノの大発見：ソートアルゴリズムの計算量は O(n) だった！？

元ネタはここらへん。

読んでみたけど、なんかおかしくね？

このループの回数、見てのとおり常に一定です。上の22というのは、これだけ繰り返せば必ずdoubleの精度に収まるというマジックナンバーです。詳しくは奥村本をご覧ください。
404 Blog Not Found:アルゴリズム百選 - ベキ乗はO(1)でOK?

これはつまり、n に「doubleの精度」という制限をかけて、その範囲でなら O(1) だと主張しているようだ（だから『高々22回繰り返せば良い』といっているのだろう）。

しかしこれは間違いじゃないだろうか。この『22』というマジックナンバーは、n についての制限を取っ払ったらきっと増えていくんじゃない？もしそうなら、この『22』は定数ではなくなるので、O(1) だという根拠にはならなくなる。

例えば、ソートのアルゴリズムは一般的に O(n*log(n)) であることが知られている。ここで n <= 10,000 という制限をつけたとしよう。この場合、log(n) は高々 14 である。つまり O(n*log(n)) は O(n*14) となる。「14」は定数だから表記上は無視して、これは結局 O(n) と表せる。なんと、ソートの計算量は O(n) だったのだ！

同じように探索アルゴリズムを考えてみる。探索アルゴリズムの計算量は一般に O(log(n)) であることが知られている。ここで n <= 10,000 の制限を適用すると、log(n) は高々 14 なので、これは O(14) と書ける。定数は無視できるから、結局探索アルゴリズムの計算量は O(1) であることが証明された！

・・・

これが本当ならチューリング賞モノの大発見である。懸命な読者なら分かってると思うが、もちろんこれは大間違いだ。「14」という数字は、n <= 10,000 という制限をつけたときの log(n) の最大値であって、定数ではない。これを定数だと見なしてしまったことが上の間違いの原因である。

元記事の『22』というマジックナンバーも、これと同じじゃないだろうか。『22』は定数でもなんでもなく、『doubleの精度』という制限を付けた場合の、何らかの式の値であって、制限を外した場合はきっと増えていくんだろう。

ただ、n と比べて log(n) は極めて小さい値になるので、定数に近似する考え方はありだろう。しかしそれをするともはや計算量としては正しくないので、計算量の話とは別物として考える必要がある。違いが分かってないうちは止めた方がいいと思う。

その意味では、

アルゴリズム解析が教える計算量と、計算機で実際に計算する場合の計算時間の傾向が違うというのはよくあることで、経験の豊富な方が後者について詳しく解説することの意義は大きいと思います。（アーキテクチャに精通していない私には難しいです。）
ただ、O記法とカジュアルなO記法は見た目の区別がつかないので（注釈を読み落とす危険もありますし）、後者については別な記法を導入した方が、潜在的な読者の混乱を未然に防げるのではないでしょうか。
カジュアルなO記法 | 配電盤

という意見に賛成。

最後に・・・東スポみたいなタイトルつけてすまんかった。