オーダー表記

日付がわかってからまだ寝てない.今から寝る.多分今日中に起きないので寝る前に日記を書いてしまう.

日付が変わるまでは論文書きと,追加のデモ実装.以外に捗る.

んで,午後は某所にて某発表を聞いた.んで,その発表の本質とはあまり関係ないが,そこでおこった議論.

  • 「計算量の下界が \mathrm{O}(n^{3})って何も言ってないに等しくない?」

うーむ,たしかに 0 = \mathrm{O}(n^{3})なので,「計算量の下界が 0」を含意しているようにも読める.すると「計算量なんだからそりゃ正なのは当たり前だろ」という話になって,何も言ってないに等しい(ということだと理解したけど,そういうことだったのか?)

  •  \mathrm{O}(n^{3 - \varepsilon})と言われたときに,どう思えば良いのか?」

頭がこんがらがる話だ.「  \mathrm{O}(n^{3}) でないことは確実にわかるが,例え \mathrm{O}(n^{2.9999999})かもしれないし, \mathrm{O}(n^{2.9999999999999999})かもしれない」みたいな話だろうか? よく見かけるが(自分が不勉強なせいで)いまいちよくわかっていない.

んで,これと関係して,今日の話とは別の話だが,一家言ある話.

  •  n^{2} + n \log nを最も適切な \mathrm{O}記法を使って表せ」

「最も適切な」ってなんだろう.私の理解では, \mathrm{O}(n^{2})はもちろん, \mathrm{O}(n^{2} + n \log n)でも \mathrm{O}(n^{100})でも,なんなら \mathrm{O}(n^{n})とか書いても○にすべきなはずだが,どうなるのだろう. \mathrm{O}の定義を正しく理解しているかどうか問いたいなら,もう少し適切な出題方法がある気がするし(例えば選択式にするとか,もう少し形を「きちんとした言葉で」指定するとか),そうでなくて単に関数の増加の速さを比較して欲しいだけなら,愚直にそういう問題を出せば良いのではないかという気がする.せめて \Theta記法で書かせる方が適切なのではないか.

やはり \mathrm{O}記法に欠陥が多いのだという気もする.この \mathrm{O}ってなんだろう? 昔Twitterで「higher-order function だと思えば良いのでは」といわれたが, n^{2} = \mathrm{O}(n^{2})とか 2n^{2} = \mathrm{O}(n^{2})とか書くので関数の要件を満たさないから higher-order function でもないし,monadic relation でもない.強いて言えば, X = \mathrm{O}(Y) X Yの2項関係である,ということかね.だとしたら記法として気持ち悪い気がする.普通に \simみたいな同値関係で書けば良いのではなかろうか.

閑話休題.それにしても, \Thetaとか \Omegaとか全然使われないのはなぜだろう?