いい機会なのでお断りしておくと、

O(1)というのはご機嫌に速いということ？ by Inquisitor
たとえばn桁の足し算は、2つの整数および結果が適当なレジスタに収まるうちは、1クロック（程度）でできるのでご機嫌に速いわけですが、O(1)というわけではもちろんなく、O(n)だと考えるのがふつうでしょう

それが「ふつう」だという人向けの本にするつもりはありません。

本書はなるべく正確な知識を提供することを目指しますが、その正確さのためにページ数が倍になるのであればそれを恐れずに割愛するつもりでもあります。脚注や参考文献など、「より正確な知識のため」のポインターはその場合なるべく明示するつもりではありますが。

厳密に言えば、こういう言い方は許されないはずです。精度に限りがあるのなら、結果の入ったテーブルを使うことで、どんな関数でもご機嫌に速く計算できます。もっとも、テーブルを作るのに時間がかかるわけですが

はい。それではdoubleの引数一つを取ってdoubleを返す関数のために、lookup tableを用意して下さいな。必要なメモリーはほんの264です。これだけtableが大きいと、テーブルアクセスもO(1)で済むかどうかは疑問ですが。それでやっと関数一つです。

厳密には、「最初の1回だけO(n)になる」というような表現は許されないはずですが

これが許されないのであれば、クイックソートのアルゴリズムを吟味するのに「通常O(n log n)、最悪の場合でO(n2)」という言い方も許されなくなります。逆に、O記法の定義に則れば、多項式時間アルゴリズムはすべてO(2n)という言い方も厳密に正しいということになります。

こういう過度にpedanticな姿勢が、どれだけ多くの潜在読者を遠ざけているか、つっこみを入れるみなさんは考えたことはあるのでしょうか。アルゴリズムを語る人は少なくないのに、本にまでなることは滅多にない事情はこのあたりに由来するのではないかと思います。

とはいえ、pedantic な部分がまるで不要かというとそうでもありません。そのあたりの落としどころが難しいところですし、私もまだどこまで pedantic に、あるいはどこまで「いいかげん」に書くかは決めあぐねています。

一つ参考にしているのが、Mastering Algorithms with Perl。同書では私がやっている以上にカジュアルなO記法が見られる一方、O記法の説明のところでOだけではなくΘやΩも紹介し、それらが実地においてどうインパクトを与えるのか図とグラフで説明した上で、「もっと厳密に知りたい人はこちら」と参考文献へのポインターを示しています。

その流れで、より厳密なO記法をコラムとして書くことはあるでしょう。しかし全体の調子はなるべくカジュアルなものにしておきたいのです。

そこのところ、よろしくお願いします。

ところでどなたか、シェルソートがO(?)なのかご存じの方はいらっしゃらないでしょうか。O(n (log n)2)という人もいるし、O(n1.25)という人もいるし....

Dan the Practical Author