競技プログラマでも $O$-notation についてもうちょっとちゃんと考えたかった話

はじめに

　アルゴリズムの計算量を表現するツールとして，$O$-notation というのは競技プログラミングの文脈でもよく出てきます．その一方で，$O$-notation の導入が「ふわっ」と行われるケースはかなり多く，厳密に定義して導入する場面というのが実は少ないようにも見受けられます．それはそれで敷居が低くなってよいのですが，定義や notion に誤解があるとコミュニケーションで齟齬を生ずる可能性もあるかと思います．実際，$O$-notation の定義からすると「それっておかしくない？」と感じるような使用例もしばしば見受けられます．例えば「$O(1{,}000{,}000{,}000 )$」だとか，「この処理には少なくとも $O( f(n) )$ かかる」などです．
　競技プログラミングに取り組む場面においてこの手の不理解が致命的な事態をもたらすことはあまりありませんが，テクニカルタームを用いたコミュニケーションで齟齬を生まないためには定義をしっかり抑えておくべきだと思いますので，本稿ではそのあたりについて書いてみようと思います．ですので，先程の例に対して「それって $O( 1 )$ じゃん」とか「$\Omega$ で書けばよくない？」と言える人は，この記事を読んでも既知の事柄ばかりかもしれません*1．数式が登場しますが，読み方やお気持ちも一緒に書いていきますので，見た目で「うっ」とならずにいただけるとありがたいです．

O-notation

　$O$-notation を雑に使っている人の多くは，「処理時間が $O( * )$ のカッコ内にあるやつの定数倍に比例する」ぐらいの意味で使っているかと思われます．しかしこれは $O$-notation の定義からすると必ずしも正しくありません．実際には，$O$-notation は（処理時間についての文脈で使うなら）処理時間の上界にしか言及していません*2．$O( n^3 )$ 時間で動作するアルゴリズムを $O( n^5 )$ 時間アルゴリズムだと主張しても，それは正しい主張です*3．
　では，$O$-notation の定義を見てみましょう．"Introduction to Algorithms" [1] では，以下のような感じで定義されています（やや書き方を変えています）．
$$
O( g( n ) ) \overset{ \mathrm{ def } }\Longleftrightarrow \{ f( n ) \mid \exists c, \exists n_0, \forall n \geq n_0, 0 \leq f( n ) \leq c g( n ) \}
$$
ここで，$f, g$ は関数です．また，$O( g( n ) )$ は関数 $g( n )$ によって定まる関数の集合であるという点には注意しておいた方がよいかもしれません．関数 $f( n ) \in O( g( n ) )$ であるような関数 $f( n )$ というのはどういう関数かというと，右辺の内包表記を丁寧に読んであげれば，

• ある定数 $c$ と $n_0$ をうまくとってあげたとき，
• $n_0$ 以上の全ての $n$ に対して，
• $f( n ) \leq cg( n )$ である……つまり，$f( n )$ の値は $g( n )$ の定数（$c$）倍以下である

ような $f( n )$ です．お気持ちとしては，「引数 $n$ が小さいところでの振る舞いは置いておいて（$n \geq n_0$ が表現している），ある程度大きな $n$ に対しては常に $f( n )$ は $g( n )$ の定数（$c$）倍以下である」という感じです．また，よく見かける $f( n ) = O( g( n ) )$ という風な表記は記号を厳密に使えば $f( n ) \in O( g( n ) )$ ですので等号の左右を交換できません．この意味で等号がもっていてほしい性質をもっていない（というか本来等号ではない）のですが，この「記号の濫用」*4はよく行われています*5．

冒頭に挙げた誤用（？）の話

　さて，冒頭で $O( 1{,}000{,}000{,}000 )$ や「少なくとも $O( n )$ 時間必要」は変であると書きました．これらについて $O$-notation の定義を踏まえて観察してみたいと思います．

$O( 1{,}000{,}000{,}000 )$ ?

　$O( 1 )$ という集合を考えて，$\exists c$ のところで $c = 1{,}000{,}000{,}000$ とし，$O( 1{,}000{,}000{,}000 )$ の側では $c = 1$ ととってあげると，$c g( n )$ のところが一致して $O( 1{,}000{,}000{,}000 )$ と等しくなりますので，集合として同じにできます．これについては「間違い」ということではありませんが，通常，カッコの中は簡単な形の式になるように書かれることが多く，また，大きな定数を書くことによって特段何かを伝えたかったとしても，定義的には伝わらないということになります．

「少なくとも $O( n )$ 時間必要」？

　こちらについては，例えば $O( 1 ) \subseteq O( n )$ だったりすることに注意すると，「少なくともこれだけ必要」みたいなお気持ちがあんまり正しく表現されていません．$O$-notation は「これ以下」を表しているのに対して，「少なくとも～～かかる」は「これ以上」という気持ちを表現しているためです．

アルゴリズム分野での $O$-notation

　アルゴリズムの文脈では典型的には前節の定義式における関数 $f$ は「入力サイズ」を「必要リソース（時間 or 空間）」へ写す関数です．時間の意味でのリソースはそのまま実行時間のことを言っていて，空間というのは必要なメモリの量のことを言います．
　競技プログラミング含めアルゴリズム分野で $O$-notation を使って「このアルゴリズムは $O( g( n ) )$ 時間である」といった主張をしたとき，この主張をちゃんと言うと，

• 着目しているアルゴリズムの実行時間は，アルゴリズムへの入力のビット長を $n$ として関数 $f( n )$ で表され，$f( n ) \in O( g( n ) )$ である

などの意味で用いられます．また，グラフアルゴリズムでは「グラフの頂点数から実行時間への関数」だったり，数論アルゴリズム（って呼び方でいいのかな？）*6では「入力が表現している整数 $n$ から実行時間への関数」であったりします．詳細は省きますが，本来というか，原義的には「チューリングマシンへの入力長」から「実行時間への関数」ですので*7，ちょっと注意しておく必要があります*8．
　また，前節最後の「引数 $n$ が小さいところでの振る舞いは置いておいて，ある程度大きな $n$ に対しては常に $f( n )$ は $g( n )$ の定数倍以下である」というのは，アルゴリズムと絡めて例を挙げると，例えば $O( n \log n ) \subseteq O( n^2 )$ という事実は，「配列をソートするとき，ある程度大きい配列に対しては $O( n \log n )$ のマージソートが優秀だが，入力が小さいと $O( n^2 )$ の挿入ソートが速いかもしれない」といった感じです*9．基本的には，

• 入力サイズ $n$ を無限に大きくしていったときに，必要リソース量 $f( n )$ は入力サイズの増大に対応してどのように増えていくのか？

という点に着目しています．なので，例えば，「入力サイズに関わらず常に 2 分間で値を探索するアルゴリズム」があったとすれば，それは $O( 1 )$ 時間アルゴリズムです．$O( 1 )$ 時間というと「一瞬で終わる」というイメージがありますが，正しくは「入力長に依存しない」ぐらいの意味なので注意が必要です．入力長が無限に大きくなっても常に「定数時間」なのはある意味「一瞬」ではあるのですが……．

$\Omega$-notation と $\Theta$-notation

　ここまで見てきたように，$O$-notation は「上界」を表しています．先程あげた「少なくともこれぐらいの時間がかかる」などを言いたいときには「下界」を表現できる記号があると便利です．下界は記号 $\Omega$ を使って $\Omega( g( n ) )$ などと書きます．定義としては $O$-notation とほぼ同様で，
$$
\Omega( g( n ) ) \overset{ \mathrm{ def } }\Longleftrightarrow \{ f( n ) \mid \exists c, \exists n_0, \forall n \geq n_0, 0 \leq c g( n ) \leq f( n ) \}
$$
です．$O$-notation との違いは，内包表記の一番右で $f( n )$ と $c g( n ) )$ の位置が入れ替わっているだけです．$O$-notation と同様丁寧に読んであげれば，

• ある定数 $c$ と $n_0$ をうまくとってあげたとき，
• $n_0$ 以上の全ての $n$ に対して，
• $c g( n ) \leq f( n )$ である……つまり，$f( n )$ の値は $g( n )$ の定数（$c$）倍以上である

となります．
　また，$O( g( n ) )$ と $\Omega( g( n ) )$ の共通部分を，記号 $\Theta$ を使って，
$$
\Theta( g( n ) ) \overset{ \mathrm{ def } }\Longleftrightarrow O( g( n ) ) \cap \Omega( g( n ) )
$$
と書きます．$f( n ) \in \Theta( g( n ) )$ と表明すれば，上界と下界の両方から抑えることができて，「定数倍に比例する」に近い気持ちを表現したいときにより適切な記法となります．

平均とか最悪とか

　$O$-notation は関数の（発散速度の）上界に言及すると書きました．「上界」は「これ以下」に近いような気持ちの言葉ですが，だからといって，$O$-notation で表された計算量が，対象のアルゴリズムが最大で利用する計算リソースとは限りません．これは，アルゴリズムの平均計算量を表現するのか最悪計算量を表現するのかによって変わってきます．クイックソートを例にすれば，

• クイックソートの平均計算量は $O( n \log n )$ 時間
• クイックソートの最悪計算量は $\Theta( n^2 )$ 時間

という 2 つの主張はそれぞれ正しいです．競技プログラミングでは競技の性質上専ら最悪計算量についての話をしますが，本来は何について話をしているかも意識する必要があります．

おわりに

　いわゆる漸近記法について，競技プログラミングで頻出の $O$-notation から，あると議論（表現）がしやすい $\Omega$-notation, $\Theta$-notation まで眺めてきました*10．本稿が理解の助けとなりましたら幸いです．

参考文献

[1] Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009.

*1:それはそれとして，内容の不備等への指摘は歓迎です

*2:i.e. 「大きくてもこれぐらい」という話であって，必ずしもその大きさになるとは限らない

*3:もちろん，「よりよい上界」が知られているならそちらで表記した方が好ましくはあります．とはいえ，解析が甘い事によって指数が大きいアルゴリズムや，解析の改善だけで計算量が改善される論文も出ているようです（指導教官氏から存在性だけを聞いたので refer しません＞＜

*4:「記号の濫用」でテクニカルタームらしく Wikipedia 先輩に記事が立ってますね

*5:あまり好きではありませんが

*6:素数判定とかそういうやつ

*7:チューリングマシンだと議論が煩雑なので他の「計算モデル」を使うことの方が多い気がしますが，色々面倒なのでその辺は割愛します

*8:なので，「整数」などが入力になっているとき，整数 $x$ のビット長というのはその整数の $\log x$ 程度なので，本来は気をつけて議論する必要があります．「擬多項式時間」などで調べてみましょう

*9:この例だとクイックソートは出しにくいけど，イントロソートとか言いたくない……

*10:実は $o$-notation と$\omega$-notation もあるのですが Wikipedia 先輩に任せます