カジュアルなO記法

O(1)というのはご機嫌に速いということ? の続き。

アルゴリズム解析が教える計算量と、計算機で実際に計算する場合の計算時間の傾向が違うというのはよくあることで、経験の豊富な方が後者について詳しく解説することの意義は大きいと思います。(アーキテクチャに精通していない私には難しいです。)

ただ、O記法とカジュアルなO記法は見た目の区別がつかないので(注釈を読み落とす危険もありますし)、後者については別な記法を導入した方が、潜在的な読者の混乱を未然に防げるのではないでしょうか。

「すでに2つの意味で使われているのだからしょうがない」ということもあるかもしれません。でも、世界をどちらの方向に動かしたいかと言えば、後者の意味ではO記法が使われない方向です。(自分が間違って使っていたら直したいです。)

補足

はい。それではdoubleの引数一つを取ってdoubleを返す関数のために、lookup tableを用意して下さいな。必要なメモリーはほんの2^64です。(用語の定義、またはその欠如)

例がよくなかったようです。言いたかったのは、「入力が大きくなったときに残る主要素」を見るというのが基本的なアイディアの一つなので、精度を限ったときにまで無理にO記法を使わなくてもいいのではないか、ということです。

クイックソートのアルゴリズムを吟味するのに「通常O(n log n)、最悪の場合でO(n^2)」という言い方も許されなくなります。(用語の定義、またはその欠如)

(潜在的な読者のためにわざと誤解したふりをしてるんだろうなあと思いつつ)「計算量が状況によって変わる」というところまで一般化して「許されない」と言いたかったわけではなく、「入力が同じなのに計算量が状況によって変わる」ということに対して「許されないはず」と言いたかったのです(ランダム性が入ると少し違うかもしれませんが)。

「あるソートアルゴリズムがあって、あらかじめソートした系列 {1,2,・・・,N} を与えたときの計算量が、最初はO(n^2)で、2回目からはO(n log n)になる」とか。

「厳密には」と言って少し厳密にしたつもりでしたが、もっとpedanticに書かないと誤解される危険がありますね。

参考:Hyukiさんのコメント

続き:ベンチマークに迷う

2 thoughts on “カジュアルなO記法

  1. 入力が同じなのに計算量が状況によって変わる」ということに対して「許されないはず」
    これに関しては、exactなアルゴリズムであっても、計算量が入力だけでなく出力に依存するoutput sensitiveなものがあるので、「許されないはず」というのは間違いです。

  2. kenさん、コメントありがとうございます
    なるほど、私もいいかげんだったということですね

コメントは停止中です。