計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。
数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。
それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。
TL; DR
- 関数の増加度合いのことをオーダーと呼ぶよ
- 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ
- オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ
- オーダーを上下両方から抑えたいときは \(\Theta\) を使うよ
- これを \(O\) だと思っている人がたくさんいるよ
- 適切な文脈で適切な記号を使えるとえらいね
まえがき
そもそも、特に競技プログラミングの文脈では、計算量は最初の段階で基礎的な事項としてふわっと教えられることが多いです。
そのためかあまり厳密に教えられることはなく、その後も自分で詳しく学ぶ人は多くはない印象です。
そうした人がさらに不正確な内容の記事を書いていることも多いです*2。
以下では、まず計算量を考える動機を述べてから、計算量の定義とそれに関する記法の導入をします。さらに、計算量に関するよくある誤解・誤用についても述べます。不勉強な人がよく陥る誤用とは別に、学術的な文脈でもよく行われる濫用もあり、それについても述べます。
多少長めの記事ですが、ある程度の根気を持って読んでいただけたらと思います*3。
もちろんこれは計算量について学びたい人（あるいは学ぶ必要が出てきた人）に対する記事であって、読みたくない人に向けた記事ではないです*4。
本題
注意：以下で定義されるまでは、「計算量」という概念を忘れて読んでみてください*5。
導入・動機
たとえば、長さ \(n\) の整数の配列 \(a = (a_1, a_2, \dots, a_n)\) をソートしたくなったとします。
以下の 3 つのアルゴリズム*6を教えられて、好きなものを実行すればよいことになりました。
アルゴリズム 1 は次の通りです。
- for \(i\) in \(1, \dots, n-1\)
- // \( (a_i, \dots, a_n)\) の最小値を探し、\(a_i\) と交換する。
- \(i' \gets i\) // 今まで見た最小値の添字
- for \(j\) in \(i+1, \dots, n\)
- if \(a_{i'} \gt a_j\)
- \(i' \gets j\)
- \(x \gets a_i\)
- \(a_i \gets a_{i'}\)
- \(a_{i'} \gets x\)
アルゴリズム 2 は次の通りです。
- for \(j\) in \(2, \dots, n\)
- \(x \gets a_j\)
- \(i \gets j-1\)
- // \( (a_1, \dots, a_{j-1})\) がソート済み。適切な位置に挿入する。
- while \(i\ge 1\) and \(a_i \ge x\)
- \(a_{i+1} \gets a_i\)
- \(i \gets i-1\)
- \(a_i \gets x\)
アルゴリズム 3 は次の通りです。
- 長さ \(n\) の未初期化の配列 \( (b_1, \dots, b_n)\) を用意する
- for \(e\) in \(1, \dots, \infty\)
- \(l \gets 2^e\)
- // 長さ \(l/2\) の隣り合うソート列から長さ \(l\) のソート列を作る
- for \(i\) in \(0, \dots, \lceil n/l\rceil-1\)
- \(i_l \gets i\cdot l\)
- \(i_r \gets \min\{n, i_l+l/2\}\)
- \(e_l \gets i_r\)
- \(e_r \gets \min\{n, i_l+l\}\)
- \(j \gets i_l\)
- while \(i_l \lt e_l\) and \(i_r \lt e_r\)
- if \(a_{i_l} \lt a_{i_r}\)
- \(b_j \gets a_{i_l}\)
- \(i_l \gets i_l+1\)
- else
- \(b_j \gets a_{i_r}\)
- \(i_r \gets i_r+1\)
- \(j \gets j+1\)
- for \(i'\) in \(i_l, \dots, e_l -1\)
- \(b_{j+i'-i_l} \gets a_{i'}\)
- for \(i'\) in \(i_r, \dots, e_r-1\)
- \(b_{j+i'-i_r} \gets a_{i'}\)
- for \(i'\) in \(i\cdot l, \dots, e_r-1\)
- \(a_{i'} \gets b_{i'}\)
- if \(l \ge n\)
- break
各アルゴリズムのお気持ち概要（クリックして展開）
お気持ち概要とソートされていくイメージみたいなのを書いておきます。[] の部分がソートされているのが保証されている部分です。
Algorithm 1：最小値を探して一番左に置く。残ったものから最小値を探してさっきの最小値の隣に置く。というのを繰り返す。
input: 8 2 7 6 4 5 3 1
[1] 2 7 6 4 5 3 8
[1 2] 7 6 4 5 3 8
[1 2 3] 6 4 5 7 8
[1 2 3 4] 6 5 7 8
[1 2 3 4 5] 6 7 8
[1 2 3 4 5 6] 7 8
[1 2 3 4 5 6 7] 8
[1 2 3 4 5 6 7 8]
Algorithm 2：左端からソート列を作って伸ばしていく。今までできていたソート列の適切な位置に新たな要素を挿入するというのを繰り返す。
input: 8 2 7 6 4 5 3 1
[8] 2 7 6 4 5 3 1
[2 8] 7 6 4 5 3 1
[2 7 8] 6 4 5 3 1
[2 6 7 8] 4 5 3 1
[2 4 6 7 8] 5 3 1
[2 4 5 6 7 8] 3 1
[2 3 4 5 6 7 8] 1
[1 2 3 4 5 6 7 8]
Algorithm 3：隣り合う要素でペアを作り、長さ 2 のソート列たちを作る。隣り合う長さ 2 のソート列を適切な順でくっつけて、長さ 4 のソート列たちを作る。これを繰り返してソート列の長さを倍々に増やしていく。
input: 8 2 7 6 4 5 3 1
[2 8] [6 7] [4 5] [1 3]
[2 6 7 8] [1 3 4 5]
[1 2 3 4 5 6 7 8]
（クリックして展開部分おわり）
さて、多くの状況であれば、最も早く終了するアルゴリズムを使いたいはずです。
別に最も遅く終了するものを選んでもいいですが、なんにせよ、各々どのくらいかかるのかわからないことには選べません*7。
別の例として、上記アルゴリズム 1 を使って苦しんでいる人に対して「アルゴリズム 3 の方が効率がいいですよ」と教えたいときにも、そうした指標がないことには説得がしにくいわけです。もちろん、教えられる側もその指標を知っているのが望まれます。
解析の例
そこで、各行に対して「それを実行するための時間」と「その実行回数」の積を調べ、その合計をそのアルゴリズムの時間計算量と呼ぶことにします。
時間計算量が小さいほど最も早く終了することになります。
各行を実行するための時間は、演算の種類や（現実に即して言えば）CPU の性能などによりますが、ある定数だとして「\(i\) 行目の実行には \(c_i\) かかる」ということにします*8。
アルゴリズム自体はパソコンとは独立な概念（手などで実行することもできますし）なので、アルゴリズムの評価をする際に CPU などに依存したような表現はしたくないという気持ちもあります。
なお、定数時間でできることにする命令セットはその時々の状況に応じて適切に設定しましょう。ここでは配列へのアクセスや四則演算・大小比較、代入などを仮定しています。
とすると、各アルゴリズムの時間計算量は次のようになります。
アルゴリズム 1 の表
| コード |
コスト |
回数 |
| for \(i\) in \(1, \dots, n-1\) |
\(c_1\) |
\(n\) |
| \(i' \gets i\) |
\(c_2\) |
\(n-1\) |
| for \(j\) in \(i+1, \dots, n\) |
\(c_3\) |
\(\sum_{i=1}^{n-1} (n-i+1)\) |
| if \(a_{i'} \gt a_j\) |
\(c_4\) |
\(\sum_{i=1}^{n-1} (n-i)\) |
| \(i' \gets j\) |
\(c_5\) |
\(\sum_{i=1}^{n-1} t_i\) |
| \(x \gets a_i\) |
\(c_6\) |
\(n-1\) |
| \(a_i \gets a_{i'}\) |
\(c_7\) |
\(n-1\) |
| \(a_{i'} \gets x\) |
\(c_8\) |
\(n-1\) |
ここで、for \(i\) in \(1, \dots, n-1\) については、ループの中に入るための \(n-1\) 回とループを抜けるための
\(1\) 回を合わせて \(n\) 回実行されるとします。
また、if の内部は入力によって実行回数が変わるので、各 \(i\) に対する実行回数を \(t_i\) (\(0\le t_i\le n-i\)) とします。
\(\sum_{i=1}^{n-1} (n-i)\) の部分は、各 \(i\) に対して \(n-i\) 回実行されるので、それの合計ですということです。
よって、この時間計算量 \(T_1(n)\) は次のようになります*9。
\[
\begin{aligned}
T_1(n) &=
c_1\cdot n + (c_2+c_6+c_7+c_8)\cdot(n-1) + c_3\cdot\sum_{i=1}^{n-1} (n-i+1) + c_4\cdot\sum_{i=1}^{n-1} (n-i)
+ c_5\cdot\sum_{i=1}^{n-1} t_i \\
&= (c_1+c_2+c_3+c_6+c_7+c_8)\cdot n - (c_2+c_3+c_6+c_7+c_8)\cdot 1 + (c_3+c_4)\cdot\sum_{i=1}^{n-1}(n-i) + c_5\cdot\sum_{i=1}^{n-1} t_i\\
&= (c_1+c_2+c_3+c_6+c_7+c_8)\cdot n - (c_2+c_3+c_6+c_7+c_8)\cdot 1 + (c_3+c_4)\cdot\frac{1}{2}\cdot n(n-1) + c_5\cdot\sum_{i=1}^{n-1} t_i\\
\end{aligned}
\]
係数が冗長なので、適宜置き直して次のようになります。
\[
T_1(n) = a_2\cdot n^2 + a_1\cdot n + a_0\cdot 1 + a_t\cdot\sum_{i=1}^{n-1} t_i
\]
ここで、\(\sum t_i\) の部分に関して、最も小さくなるときは \(0\)、最も大きくても 2 次式なので、次のようになります。
\[
a_2\cdot n^2 + a_1\cdot n + a_0\cdot 1 \le T_1(n) \le b_2\cdot n^2 + b_1\cdot n + b_0\cdot 1
\]
ここで、\(n\) が十分大きくなったとき、\(a_1\cdot n+a_0\cdot 1\) は \(a_2\cdot n^2\) と比べて十分に小さくなります。
なので、最も影響の大きい \(a_2\cdot n^2\) の項にのみ着目したいです*10。
\(n\) が十分大きくなったときに最も影響の大きい項を支配項、無視できる項を非支配項と呼ぶことにします*11。
\(T_1(n)\) の支配項が \(a\cdot n^2\) であることを、後でちゃんと定義する記法を用いて \(T_1(n)\in\Theta(n^2)\) や \(T_1(n)=\Theta(n^2)\) と書きます*12。
\(a_2\cdot n^2 + a_1\cdot n + a_0\cdot 1\in\Theta(n^2)\) と \(b_2\cdot n^2 + b_1\cdot n + b_0\cdot 1\in\Theta(n^2)\) が成り立ちます。すなわち、アルゴリズム 1 の時間計算量 \(T_1(n)\) に対して、\(T_1(n)\) が最も小さいとき（最良時 (best case)）\(T_1(n)\in\Theta(n^2)\)、最も大きいとき（最悪時 (worst case)）\(T_1(n)\in\Theta(n^2)\) が成り立ちます。
アルゴリズム 2, 3 についての議論は、長くなったので折りたたんでおきます。
アルゴリズム 2, 3 についての議論（クリックして展開）
アルゴリズム 2 の表は次の通りです。
| コード |
コスト |
回数 |
| for \(j\) in \(2, \dots, n\) |
\(c_1\) |
\(n\) |
| \(x \gets a_j\) |
\(c_2\) |
\(n-1\) |
| \(i \gets j-1\) |
\(c_3\) |
\(n-1\) |
| while \(i\ge 1\) and \(a_i \ge x\) |
\(c_4\) |
\(\sum_{j=2}^n (u_j+1)\) |
| \(a_{i+1} \gets a_i\) |
\(c_5\) |
\(\sum_{j=2}^n u_j\) |
| \(i \gets i-1\) |
\(c_6\) |
\(\sum_{j=2}^n u_j\) |
| \(a_i \gets x\) |
\(c_7\) |
\(n-1\) |
\(u_j\) は while 文の中の実行回数のための変数で、\(0\le u_j\le j-1\) です。
アルゴリズム 1 同様に、適宜変数を置き直して、時間計算量 \(T_2(n)\) は次のようになります。
\[
T_2(n) = a_1'\cdot n + a_0'\cdot 1 + a_t'\cdot\sum_{j=2}^n u_j
\]
ここで、\(\sum u_j\) の部分に関して、最良時は \(u_j = 0\) なので、\(T_2(n) = a_1'\cdot n+a_0'\cdot 1\) となり、\(T_2(n)\in\Theta(n)\) となります。
最悪時は、入力が降順に並んでいるとき \(u_j = j-1\) で \(\sum_{j=2}^n (j-1)\) は 2 次式となるので、\(T_2(n) = b_2'\cdot n^2+b_1'\cdot n+b_0'\cdot 1\) となります。すなわち、\(T_2(n)\in\Theta(n^2)\) です。
読者の課題にしたいところですが、アルゴリズム 3 についても行います。
| コード |
コスト |
回数 |
| for \(e\) in \(1, \dots, \infty\) |
\(c_1\) |
\(v\) |
| \(l \gets 2^e\) |
\(c_2\) |
\(v\) |
| for \(i\) in \(0, \dots, \lceil n/l\rceil-1\) |
\(c_3\) |
\(\sum_{e=1}^v (\lceil n/2^e\rceil+1)\) |
| 省略 |
- |
- |
| \(e_r \gets \min\{n, i_l+l\}\) |
\(c_7\) |
\(\sum_{e=1}^v \lceil n/2^e\rceil\) |
| 省略 |
- |
- |
| for \(i'\) in \(i\cdot l, \dots, e_r-1\) |
\(c_{21}\) |
\(\sum_{e=1}^v \sum_{i=0}^{\lceil n/l\rceil-1} (e_r-i\cdot l+1)\) |
| \(a_{i'} \gets b_{i'}\) |
\(c_{22}\) |
\(\sum_{e=1}^v \sum_{i=0}^{\lceil n/l\rceil-1} (e_r-i\cdot l)\) |
| if \(l \ge n\) |
\(c_{23}\) |
\(v\) |
| break |
\(c_{24}\) |
\(1\) |
\(\lceil x\rceil\) は、\(x\) 以上の最小の整数です。
若干怪しいですが、長さ \(n\) の未初期化の配列を用意する時間は無視できることにします。
あるいは \(c_0\cdot n\) 時間としてもいいです。どうせ支配的にならないので（もっと大きくなるとは考えにくいし）。
1 行目の実行回数 \(v\) は、23–24 行目の分岐と break によって定まります。
\(\sum_{i=0}^{\lceil n/l\rceil-1}(e_r-i\cdot l) = n\) であり、\(v = \lceil\log_2(n)\rceil\) です。
よって、\(a_{i'}\gets b_{i'}\) の実行回数は \(n\lceil\log_2(n)\rceil\) となります。
他の行についてもこれに \(n\) が足された程度以下なので、結局、全体の時間計算量 \(T_3(n)\) は次のようになります。
\[
a''\cdot n\lceil\log_2(n)\rceil \le T_3(n) \le a'''\cdot n\lceil\log_2(n)\rceil
\]
\(a''\le a\le a'''\) なる \(a\) が存在して \(a\cdot n\lceil\log_2(n)\rceil\) と書けると言っているわけではないことに注意してください。
\(a\cdot \lceil\log_2(n)\rceil\cdot(n+b)\) のような形はこれでは表現できませんので。
よって、最良時も最悪時も \(T_3(n)\in\Theta(n\lceil\log_2(n)\rceil)\) となります。
\({}_2\) の部分と \(\lceil\rceil\) の部分を消去して、\(T_3(n)\in\Theta(n\log(n))\) と書くことが普通です。
\(\lceil x\rceil\) は \(x\) と高々 \(1\) しか変わらず、その差は支配的ではないからですね。
\({}_2\) については後述します。
（クリックして展開部分おわり）
結局、3 つのアルゴリズムに対して、最良時と最悪時は次のようになるとわかりました。
| アルゴリズム |
最良時の時間計算量 |
最悪時の時間計算量 |
| 1 |
\(\Theta(n^2)\) |
\(\Theta(n^2)\) |
| 2 |
\(\Theta(n)\) |
\(\Theta(n^2)\) |
| 3 |
\(\Theta(n\log(n))\) |
\(\Theta(n\log(n))\) |
アルゴリズム 1 の時間計算量は最良時でさえ \(\Theta(n^2)\) です。アルゴリズム 2 は最良時は \(\Theta(n)\) であり 3 つのうちで最もよさそうですが、最悪時はアルゴリズム 1 と同じく \(\Theta(n^2)\) です。
最悪時の時間計算量を小さくしたいのであれば、アルゴリズム 3 を選ぶのがよさそうです。
注意：
- \(\Theta(\bullet)\) の記法を用いる際に「\(n\) が十分大きければ」と断った通り、\(n\) が小さい場合のことはこの表からは読み取れない。
- アルゴリズム 1, 2 の最悪時はどちらも \(\Theta(n^2)\) だが、これは「これらの時間計算量が全く同じである」という主張ではない。
- これら二つの最悪時の時間計算量をより厳密に比較したいのであれば、消去した \(a_2\) などの定数倍や非支配項を考慮する必要がある。
log に慣れていない初心者向け（クリックして展開）
\(\log_2(n)\) は、\(2\) を何乗したら \(n\) になるかという値を表します。
すなわち、\(2\) を \(\log_2(n)\) 乗したら \(n\) になるということです。
たとえば、\(2^6 = 64\) なので、\(\log_2(64)=6\) です。また、\(\log_2(3) = 1.5849625{\dots}\) や \(\log_2(7) = 2.80735492{\dots}\) など、2 の冪乗以外にも定義されています。
端数を適当に切り上げたりすれば、「\(n\) を何回 \(2\) で割れば \(1\) 以下になるか？」という回数とも見なせます。
一般に、\(\log_a(n)\) は \(a\) を何乗したら \(n\) になるかを表します。
\(a\) の部分を底（てい）と呼び、底の変換公式 \(\log_a(n) = \log_a(b)\cdot \log_b(n)\) というのがあります。
適当な定数 \(\log_a(b)\) を掛けることで、\(\log_b(n)\) の部分を \(\log_a(n)\) にできるということですね。
よって、\(\log_a(n)\) も \(\log_b(n)\) も定数倍の違いしかなく、この文脈においては興味のない部分なので、省略して単に \(\log(n)\) と書かれることが多いです。\(\log_e(n)\) や \(\log_{10}(n)\) の底を省略するのとは別の事情です。
（クリックして展開部分おわり）
なお、アルゴリズム 1, 2, 3 は、それぞれ選択ソート、挿入ソート、マージソートと呼ばれているものです。
定義（+ おきもち）
計算量
上で触れてしまった通り、アルゴリズムが行った処理のコストの総和を 時間計算量 (time complexity) と呼びます。
時間計算量は入力サイズ \(n\) の関数として記述されることが多いですが、上で見た通り、入力サイズ \(n\) のみでは決まらず、入力自体によって変わることが多いです。
最も時間計算量が小さくなるような入力における時間計算量を 最良時間計算量 (best-case time complexity)、最も大きくなるそれを 最悪時間計算量 (worst-case time complexity) と呼びます。
当然、それ以外の入力における時間計算量は、最良時間計算量以上、最悪時間計算量以下となります。
（注）あるアルゴリズムにおける最悪の入力ケースは、別のアルゴリズムにおける最悪の入力ケースと一致するとは限りません。
アルゴリズム中で使用したメモリの量を指して 空間計算量 (space complexity) と呼ばれるものもあります。
アルゴリズム 1, 2 では（入力の配列を除いては）いくつかの変数しか使っていないですが、アルゴリズム 3 では長さ \(n\) の配列を用いたので、それを比べたいといったときに使うものですね。
単に 計算量 (complexity) と呼んだ場合は時間計算量を指すことが多いですが、実際には、時間や空間以外の計算リソースを指す文脈もあると思います。必要となる回路の個数とか？
「計算量は最悪時でもこれ以下ですよー」「計算量は最良時にはこれ以下になりますよー」という評価のほか、敵（？）のアルゴリズムに対して「それは最悪時にはこれ以上になっちゃいますよー」という評価もします。その評価のための武器をこれから導入します。
オーダー
さて、\(n\) の関数として計算量を記述しますが、文中で「これこれのソートの計算量は \(\frac{13}{2}n^2-\frac{5}{2}n+4\) であり〜」などと言いたくなる状況はあまりなく、支配項のみに着目して「支配項は \(n^2\) の定数倍です」といった旨の主張のみで事足りることが多いです。
支配項の定数倍を落として \(5n^2\) から \(4n^2\) に改善するよりも、支配項の増加度合いを落として \(5n^2\) から \(100n\) に改善した方がうれしいです。前者の改善では、改善後も「\(n\) が 10 倍になれば計算量は（非支配項を無視して）100 倍になる」という状況には変わりありませんが、後者の改善では「\(n\) が 10 倍になっても計算量は 10 倍にしかならない」という状況になっているためです。
ここで出てきた増加度合いのことを指して単に オーダー (order of growth) と呼びます。上記の話を言い換えると、「定数倍の削減（あるいは非支配項の改善）よりも、増加度合いの削減*13の方がうれしい」ということですね。
オーダーのちゃんとした（数学的な）定義はこれから行います。
\(\Theta\) 記法 (Theta)
といったわけで、オーダーに関する記法を導入します。
\(f(n)\) のオーダーが \(g(n)\) である（あるいは \(f(n)\) が \(g(n)\) のオーダーである）とは、次の条件が成り立つこととします。
ある定数 \(n_0\) を固定します。
これに対し、ある定数 \(c_L, c_U \gt 0\) が存在し、\(n_0\) 以上のすべての \(n\) について次の式が成り立つ：
\[ 0\le c_L\cdot g(n)\le f(n)\le c_U\cdot g(n) \]
直感的に言い換えれば、十分大きい \(n\) に対して、\(g(n)\) の定数倍で \(f(n)\) をサンドイッチできるということです。
サンドイッチできるのであれば、同じような増加度合いでしょうねといったような気持ちです。
\(f(n)\) が \(g(n)\) のオーダーであることを、\(f(n) \in \Theta(g(n))\) と書きます。\(\Theta\) は \(\theta\) の大文字で、シータ (theta) と読みます。
\(\Theta(g(n))\) というのは、オーダーが \(g(n)\) であるような関数の集合です。たとえば、次が成り立ちます。
\[
\begin{aligned}
n^2+3n &\in \Theta(n^2) \\
n^2 &\notin \Theta(n^3) \\
\Theta(2n) &= \Theta(n+1) = \Theta(n)
\end{aligned}
\]
証明（クリックして展開）
ある \(n_0, c_L, c_U\) を固定し、\(n\ge n_0\) に対して \(0\le c_L\cdot n^2\le n^2+3n\le c_U\cdot n^2\) が成り立つことを言えばよい。
\(n_0\) を十分大きく取れば \(n=0\) のことは無視できるので各々 \(n^2\) で割り、
\[ 0\le c_L\le 1+\frac{3}{n}\le c_U \]
を得る。\(n\ge 3\) のとき \(1\le 1+\frac{3}{n} \le 2\) が成り立つので、\( (n_0, c_L, c_U) = (3, 1, 2)\) とすればよい。\(\square\)
いかなる \(n_0, c_L, c_U\) に対しても、ある \(n\ge n_0\) に対して \(0\le c_L\cdot n^3\le n^2\le c_U\cdot n^3\) が成り立たないことを言えばよい。
同じく \(n^3\) で割り、
\[ 0\le c_L\le \frac{1}{n}\le c_U \]
となる。一方、\(n\gt \frac{1}{c_L}\) に対して \(\frac{1}{n}\lt c_L\) となるため、この式を成り立たせない \(n\ge n_0\) が存在する。\(\square\)
- \(\Theta(2n) = \Theta(n+1) = \Theta(n)\)
すべての \(f(n)\in\Theta(2n)\) に対して \(f(n)\in\Theta(n)\) となることなどを示せばよい。（\(n+1\) を含むペアなどに対しても同様、省略。）
「ある \(n_0, c_L, c_U\) が存在し、すべての \(n\ge n_0\) に対して \(0\le c_L\cdot (2n)\le f(n)\le c_U\cdot (2n)\) が成り立つ」とき、「ある \(n_0', c_L', c_U'\) が存在し、すべての \(n\ge n_0'\) に対して \(0\le c_L'\cdot n\le f(n)\le c_U'\cdot n\) が成り立つ」ことを示せばよい。
\( (n_0', c_L', c_U') = (n_0, 2c_L, 2c_U)\) とすればよく、おわり。\(\square\)
（クリックして展開部分おわり）
長ったらしい関数の支配項のみに注目するために \(\Theta\) を使うので、わざわざ \(\Theta(n^2+3n+1)\) などといった表記をすることは滅多にありませんが、記法自体は誤りではないです。
不等式の部分について
\(\Theta\) の定義の部分で \(f(n)\) に関する不等式を書いていますが、「ある \(n\) に対して \(f(n)\) の値がこの範囲で変動する（いろいろな値を取る）」のような意味合いではなく、単に「関数 \(f(n)\) が関数 \(g(n)\) の定数倍ではさめる」といった気持ちです。
計算量の文脈で言えば、「\(c_L \cdot g(n)\) が最良計算量で \(c_U \cdot g(n)\) が最悪計算量」のような意味合いではないので適宜注意しましょう。
「\(f(n)\) は最悪計算量とする」と固定したときに、それが \(g(n)\) の定数倍ではさめるといったことですね。
言い回しについて
なお、\(\Theta\) は計算量のみについて用いる記法ではなく、関数一般に対して用いることができる記法です。
\(\Theta\) 記法の節では計算量の話は特に出てこなかったですもんね。
たとえば、以下のような表現ができます*14。
- \(1\) 以上 \(n\) 以下の整数の総和は \(\Theta(n^2)\) である
- 要素数 \(n\) の集合に対して、空でない部分集合の個数は \(\Theta(2^n)\) 個である
- \(\Theta(n)\) applications of the binary operation
- 「二項演算 (binary operation) の \(\Theta(n)\) 回の適用 (application)」といった意味
- 足し算みたいなのを \(\Theta(n)\) 回行うというような文脈
一番上の例は、「ある関数 \(f(n)\in\Theta(n^2)\) が存在して、\(1\) 以上 \(n\) 以下の整数の総和が \(f(n)\) になる」といった意味合いです*15。一番下の例のように英語でも使われます。\(\Theta(1)\) も単数とは限らないので、\(\Theta(1)\) elements のように複数形になったりしますね。
同様に、「計算量は \(\Theta(n^2)\) です」というのは「ある \(f(n)\in\Theta(n^2)\) が存在して計算量は \(f(n)\) です」といった主張です。「計算量というのは \(\Theta(\bullet)\) の形で書かなきゃいけないのでそこに \(n^2\) を入れた」のような認識にはならないでほしいです。
自分は「計算量は \(\Theta(n^2)\) である」と言ったとき、「1+1 は 2 である」のように値を示しているのではなく、「1+1 は偶数である」のように性質を示しているという認識をしている気がします。オーダーが \(n^2\) であるというのが、その計算量の性質に対応するわけですね。
また、たとえば C++ の関数の規格では、次のような表現がよく出てきます（$\Theta$ ではなく $O$ が急に出てきますが、意味が違うだけで文法としては似た感じの使い方ができます。）。
Complexity: \(O(n\log(n))\) comparisons
比較演算以外については特に言及していませんが、比較の回数が全体のボトルネックになるので、その回数が \(O(n\log(n))\) 回だと言っているという背景があると思います*16。
比較が \(O(1)\) 時間ではない class・struct を引数とする場合のことを気にして \(O(n\log(n))\) time と書いていないという見方もあると思います。
\(O\) 記法 (big-O)
一方で、「最悪時でも計算量はここまでしか悪くならない」ということを示したいときに、わざわざサンドイッチする必要はありません。
上からだけ抑えて \(0\le f(n)\le c_U\cdot g(n)\) とさえ言ってしまえば十分です*17。それを表す記法が \(O\) です*18。
ほぼコピペですが、以下が成り立つとき、\(f(n)\in O(g(n))\) と書き、\(f(n)\) は高々 \(g(n)\) のオーダーであると言います*19。
ある定数 \(n_0\) を固定します。
これに対し、ある定数 \(c_U \gt 0\) が存在し、\(n_0\) 以上のすべての \(n\) について次の式が成り立つ：
\[ 0\le f(n)\le c_U\cdot g(n) \]
たとえば、次の式が成り立ちます。
\[
\begin{aligned}
n^2+3n &\in O(n^2) \\
n^2 &\in O(n^3) \\
n^4 &\notin O(n^3) \\
O(2n) &= O(n+1) = O(n)
\end{aligned}
\]
\(n^2\in O(n^3)\) に違和感を覚える人は、落ちついてください。
包含関係をいくつか書いてみます。
\[
O(1) \subset O(\log(n)) \subset O(\sqrt{n}) \subset O(n^{0.999}) \subset O(n/\log(n)) \subset O(n)
\]
\[
O(n) \subset O(n\log(n)) \subset O(n^2) \subset O(n^{1000}) \subset O(2^n) \subset O(3^n) \subset O(n!)
\]
\[
O(n!) \subset O( (n+1)!) \subset O(2^{2^n}) \subset \cdots
\]
たとえば \(O(n^2)\subset O(n^{1000})\) は「オーダーが高々 \(n^{1000}\) の関数すべてからなる集合は、オーダーがたかだか \(n^2\) の関数をすべて含む」「しかも、オーダーが高々 \(n^2\) ではないが高々 \(n^{1000}\) である関数は存在する」といった意味です*20。
オーダーを上から抑えているだけなので、たとえば実際には \(O(n\log(n))\) 時間のアルゴリズムを指して \(O(n^2)\) 時間ですと言ってもいいわけです。
わざわざ悪く見積もる必要はないのでは？という意見もありそうなので、例を挙げてみます。
- \(O(n^2)\) 時間で計算できる関数 \(f(n)\) と、計算量の解析が済んでいない関数 \(g(n)\) がある。
- \(f(n)\) と \(g(n)\) を一度ずつ呼び出す。
- 全体で \(O(n^2)\) 時間になっていることを示したい。
- \(g(n)\) の計算量は実際には \(\Theta(n\log(n))\) 時間だが、それをあなたはまだ知らない。
こうした状況のとき、\(g(n)\) の計算量が \(\Theta(n^2)\) より小さいことを示しても、\(f(n)\) 側が支配的になってしまいます。
\(g(n)\) の計算量が \(\Theta(n^2)\) より大きくなると \(g(n)\) 側が支配的になり全体で \(O(n^2)\) にならなくなってしまうので、そうでないことさえ示せばよいです。
そこで、\(g(n)\) が \(O(n^2)\) 時間で計算できるのを楽に示せるのなら、厳密には解析せずに「\(g(n)\) は \(O(n^2)\) 時間で計算できる」とか言ってしまってよいわけです。
この状況で「\(g(n)\) の計算量は \(\Theta(n^2)\) 時間です」とは言えないので、\(O\) を使ってサボるメリットがあるわけですね。
\(\Omega\) 記法 (big-Omega)
逆に、下から抑えたい局面もあります。
たとえば、\(O(n^3)\) 時間と言われている既存のアルゴリズムを改善し、\(\Theta(n^2)\) 時間のアルゴリズムを思いついたとします。
しかし、前述の通り \(O\) は上から抑えているだけなので、実際には（計算量解析が難しくて示せていなかったが、天才から見れば解析できたなどで）\(\Theta(n)\) 時間のアルゴリズムだったということはありえます*21。
よって、「既存のアルゴリズムのオーダーは少なくとも \(n^3\) なので、自分の \(O(n^2)\) の方が優れている」といった形で示す必要があるわけですね。そうした局面で使う記法が \(\Omega\) です。
なんちゃらの計算量は \(O(n^3)\) ですーと言ったとき、実際に最悪時 \(\Theta(n^3)\) かもしれないですけど、記法からはその情報は得られないわけですね*22。
例（クリックして展開）
\(1\) から \(n\) までの整数の素数判定をする状況を考えます。
\(i\) の素数判定は \(\sqrt{i}\) までの整数で割れるか調べればできるので、\(O(n\sqrt{n})\) 時間でできます。
これを、線形篩というアルゴリズムを用いれば \(O(n)\) 時間でできますよ〜、大改善です〜！と言った人がいたとします。
しかし、こうも考えられます。
4 以上の偶数については 2 で割った時点で素数でないことがわかります。9 以上の 3 の倍数についても 3 で割った時点でわかります。このように、小さい数で割った時点で素数でないとわかる数はたくさんありそうです。
こう考えると、実はもっと計算量は少ないのでは？という疑念も出てきますね。
実際には、\(n\) 以下の素数の個数は素数定理から \(\Theta(n/\log(n))\) 個であり、素数 \(i\) に関しては \(\Theta(\sqrt{i})\) 時間かかることなどから、\(\Omega(n\sqrt{n}/\log(n))\) 時間はかかると言えるので、改善したと言えそうです。
しかし、それを示さずに改善したと主張するのは、愚直のアルゴリズムに対して不誠実そうです。
補足：Atkin の篩は \(o(n)\) 時間だが？と言われそうな気もしましたが、それを用いて \(n\) 個の判定をするにはやはり \(\Omega(n)\) 時間かかってしまいそうです。
（クリックして展開部分おわり）
またコピペですが、以下が成り立つとき、\(f(n)\in \Omega(g(n))\) と書き、\(f(n)\) は少なくとも \(g(n)\) のオーダーであると言います。
ある定数 \(n_0\) を固定します。
これに対し、ある定数 \(c_L\gt 0\) が存在し、\(n_0\) 以上のすべての \(n\) について次の式が成り立つ：
\[ 0\le c_L\cdot g(n)\le f(n) \]
「これこれのアルゴリズムは \(O(f(n))\) 時間です」と言ったとき、常に \(O(f(n))\) 時間だと言っているように聞こえるので、worst case で \(O(f(n))\) 時間と解釈されます。また「これこれのアルゴリズムは \(\Omega(f(n))\) 時間です」と言ったとき、常に \(\Omega(f(n))\) 時間だと言っているように聞こえるので、best case でも \(\Omega(f(n))\) 時間だと解釈される気がします（文脈にもよるかも）。伝えたいことがそうでないなら、たとえば「worst case では \(\Omega(f(n))\) 時間になってしまう」のような言い方をすると誤解がないでしょう。
また、\(f(n)\in O(g(n))\) かつ \(f(n)\in\Omega(g(n))\) が言えれば、\(f(n)\in\Theta(g(n))\) が言えます。
練習として、証明してみるといいかもです*23。
Note: \(\Omega\) については、計算機科学以外ではこれと異なる定義が用いられるようなので、注意が必要かもしれません。計算機科学の文脈でも亜種はあって、\(\stackrel{\infty}{\Omega}\) などがあるようです。
\(o\) 記法 (little-o)
ある関数に対して、「この関数はそれよりもオーダーが真に小さいぞー」というのを言いたいことはありますね。
「\(T(n)\) 時間のアルゴリズムを知っているが、それよりもオーダーを改善できるのか？」といった状況などです。
そのための記法が \(o\) です*24。上記の状況では「\(o(T(n))\) 時間で解ける？」とか言えます。
これはコピペではなくて、以下が成り立つとき、\(f(n) \in o(g(n))\) と書きます。
任意の \(c_U\gt 0\) に対して、ある \(n_0\) が存在し、\(n_0\) 以上のすべての \(n\) について次の式が成り立つ：
\[ 0\le f(n) \lt c_U\cdot g(n) \]
\(O\) ではある \(c_U\) に対して抑えればよかったですが、\(o\) では任意の \(c_U\) に対して抑える必要があります*25。
たとえば、次の式が成り立ちます。
\[
\begin{aligned}
n^2 &\in o(n^3) \\
n^2+3n &\notin o(n^2) \\
n^4 &\notin o(n^3) \\
o(2n) &= o(n+1) = o(n)
\end{aligned}
\]
証明（クリックして展開）
任意の \(c_U\gt 0\) に対して、十分 \(n\) が大きければ \(0\le n^2 \lt c_U\cdot n^3\) を示す必要がある。
以前同様 \(n=0\) は除外できるので、\(0\le \frac{1}{n}\lt c_U\)。
\(n\gt \frac{1}{c_U}\) とすれば成り立つので、\(n_0=\frac{1}{c_U}+1\) としておけばよい。
例で補足：\(c_U = 0.00001\) のとき、\(n=1\) や \(n=100000\) では上式は成り立たないが、\(n=100001\) とすれば成り立つので、それを \(n_0\) とすればよい。
ある \(c_U\gt 0\) に対しては、ある \(n\le n_0\) に対して \(0\le n^2+3n \lt c_U\cdot n^2\) が成り立たないことを示す必要がある。
たとえば、\(c_U=1\) に対して、\(n\ge 0\) のとき常に \(n^2+3n\ge n^2\) なので、上式を成り立たせるような \(n_0\) は存在しない。\(\square\)
（クリックして展開部分おわり）
\(\omega\) 記法 (little-omega)
逆に、「真に大きいぞー」というのを示したいときには \(\omega\) を使います。
「このアルゴリズムは \(T(n)\) 時間だが、既存のは \(\omega(T(n))\) 時間なので、改善したぞー」といった具合です。
以下が成り立つとき、\(f(n) \in \omega(g(n))\) と書きます。
任意の \(c_L\gt 0\) に対して、ある \(n_0\) が存在し、\(n_0\) 以上のすべての \(n\) について次の式が成り立つ：
\[ 0\le c_L\cdot g(n) \lt f(n) \]
たとえば、次の式が成り立ちます。
\[
\begin{aligned}
n^2 &\notin \omega(n^3) \\
n^2+3n &\notin \omega(n^2) \\
n^4 &\in \omega(n^3) \\
\omega(2n) &= \omega(n+1) = \omega(n)
\end{aligned}
\]
記法はこの 5 種類です。5 種類の等号・不等号 \(=, \le, \ge, \lt, \gt\) と \(\Theta, O, \Omega, o, \omega\) を対応づけて認識するとよさそうです（オーダーが同じとか、オーダーが真に小さいとかいった具合です）。
記号の濫用について
濫用 について触れます。
\(2n + o(n) = O(n)\) といったような使い方はわりと頻繁になされます。
これは、「任意の \(f(n)\in o(n)\) に対して、ある \(g(n)\in O(n)\) が存在して
\(2n+f(n)=g(n)\) が成り立つ」といったように解釈されます。
疑問（クリックして展開）
上記で \(2n\) のような項がなく、\(o(n) = O(n)\) と書いてしまった場合のことを考えます。
上記の解釈であればこれは成り立ちますが、集合としては明らかに等しくないので成り立ちません。
こういう曖昧性のある式は書かない方が無難そうです。
（クリックして展開部分おわり）
\(3n = \Theta(n)\) のような使われ方もしますが、これも、\(3n\in\Theta(n)\) といったように解釈されます。
上記の例ですでに左辺からオーダーに関する記法が消去された後だと見ることもできます。
時間計算量の文脈では支配項の定数倍を気にしないことが多いので \(O(n)\) 時間などということが多いですが、空間計算量の文脈では、使用するビット数を詳細に見積もる場合もあります。
そうしたとき、たとえば \(n+cn\cdot\frac{\log(\log(n))}{\log(n)} = n+o(n)\) bits とか、\(4n\log(n)+o(n\log(n))\) bits とか言ったりします。
空間に厳しいデータ構造の研究をしている人以外には馴染みがないかもしれません。
また、「長さ \(n\) の入力を半分ずつに分けて各々同様のアルゴリズムで解き、その答えに基づいて \(O(n)\) 時間かけて元問題を解く」といった形式のアルゴリズムはよくあります。
この計算量を \(T(n)\) とおき、\(T(n) = 2\cdot T(n/2)+O(n)\) といった形の方程式を立てたりします。\(T(1)=O(1)\) として、これを解くと \(T(n)=O(n\log(n))\) となります。
よくある誤解・誤用
よくある誤解や誤用について、お気持ち表明をします。
これは正しくないですよーというのを書いていきます。ここが本編という説もあります。
引用の形式で書かれている部分が誤解の部分で、その後がお気持ち表明です。
この記事ではじめて計算量を知った人は、これらの誤用を見たことがないかもしれないので困るかもしれませんが、「そう思う人もいるんだな〜」くらいの気持ちでざっくり眺めてくれたらうれしいかもです。
\(O(f(n))\) とは \(f(n)\) に比例する計算量という意味です
\(O\) は計算量とは限らないというのをとりあえず念押ししておきます。
上記の通り、\(O(f(n))\) は \(f(n)\) の定数倍で上から抑えられるというだけで、比例するとは言っていません。
\(\Theta(f(n))\) に関しても、定数倍でサンドイッチできると言っているだけで、比例するとは言っていません。
（非支配項を無視すれば比例すると言っていい気もするので、目くじらを立てすぎかもですが、正確ではない気がします）
これ明らかに嘘で、「\(n\) が偶数なら \(2n\)、奇数なら \(3n\)」などとして定義した \(f(n)\) が反例としてあります。私が悪かったです（ぺこり）。
さておき、界隈では、\(O\) を \(\Theta\) の意味だと勘違いしている人が多い印象です。
特に競技プログラミングの文脈で、効率が十分よいか見積もるには、計算量を上から抑えれば十分なことが多く、\(O\) を使えばよいことが多いです。
特に、解析が自明な例においては、単に「これは \(O(n^2)\) 時間です」と言ったとき、実際に \(\Theta(n^2)\) 時間でもある（下からもちゃんと抑えられている）ことが多いです。
なので、そうした例を見てサンドイッチ用の記法だと勘違いするのかな？と思ったりします。
計算量とは実行時間を見積もる大雑把な指標です
計算量の表す際に大雑把な指標である \(O\) を使うことが多いですが、計算量自体が大雑把であるというのは語弊があるような気がします。
（\(O(f(n))\) を指して）オーダー \(f(n)\) と読む
\(O\) と \(\Theta\) を混同する人に多いやつですね。高々 \(f(n)\) のオーダーではなく、ちょうど \(f(n)\) のオーダーと言っているように聞こえます。
単に「オー \(f(n)\)」とか「ビッグオー \(f(n)\)」と読むのがよいはずです。英語では \(f(n)\) は f of n と読むので、big-O of f of n と読んだりするようです。
少なくとも \(O(n^2)\) のオーダーだ
「少なくとも 1000 円以下だ」という主張が不明瞭なのと同じで、怪しいです。\(\Omega(n^2)\) だと言いたがっている可能性が高いです。
\(O(n^2)\) なので効率がよくない。この \(O(n\log(n))\) の方がよい
上で \(\Omega\) を定義した際にも述べましたが、誤った使い方です。上記のように \(\Theta\) の意味で使っているんだろうなぁという気もしますが...
たとえば、「この商品は 1000 円以下なので安くない。この 400 円以下の商品の方が安い」と言われたとき、「実際には前者の商品は 200 円で、後者の商品が 300 円である状況もあり得るのでは？」という気持ちになるのと似た違和感があります。
もちろん、前者の方が高い状況も当然あり得ますが、大小比較がちゃんとできる情報が揃っていない主張だということですね。
理論的には \(\Theta(n\log(n))\) のアルゴリズムの方が効率がよいが、実測では \(\Theta(n^2)\) の方が速いこともある
別に「理論的に \(\Theta(n\log(n))\) の方が \(\Theta(n^2)\) より効率がよい」とは主張していません。
\(\Theta\) などの記法は \(n\) が十分大きいときの話で、\(n\) が小さいときに関しては特に主張していません*26。
実際、小さい \(n\) に対して非支配項や定数倍の影響を無視できないこと自体はよくあります。
どの程度大きければよいかは状況によります。
C++ のよくある標準ライブラリの実装では、サイズが小さいときには挿入ソート（導入にあるソートアルゴリズム 2）を実行したりしているようです。
計算量は \(O(\bullet)\) の形で表す・\(O(\bullet)\) は計算量のための記法である
上記で触れた通りです。どちらも、そういうわけではないです。
\(\Theta(1)\) というのは小さい定数である（という認識）
たとえば \(2+\sin(n)=\Theta(1)\) なので \(\Theta(1)\) が定数というの自体怪しい気もしますが、語弊のない文脈ではよく使われたりします。
さて、定数というのは小さい数という意味ではないです。
たとえば、「このアルゴリズムでは、\(\lfloor\log_2(n)\rfloor+\Theta(1)\) 回の関数呼び出しを行います」という仕様のアルゴリズムが実際には \(\log_2(n)+100000000\) 回の関数呼び出しをしたとしても、表記としては正しいです。
仕様に対して文句を言うのは妥当だと思いますが...*27
たとえば、「二分探索で \(\log_2(n)\) 回比較をしたあと念のため境界付近を 1 つ調べておく」「二分探索で \(\log_2(n)\) 回比較をしたあと念のため境界付近を 100000000 つ調べておく」などは、どちらも \(\log_2(n)+O(1)\) と言えてしまいそうです。
実際、C++ の std::lower_bound などの関数は、高々 \(\log_2(n)+O(1)\) 回の比較を行うと規定されており、いじわるな処理系（）では、めちゃくちゃなことになりそうだな〜という気もします。
\(\Theta(1)\) 時間というのは一発で答えが出るアルゴリズムである
たとえば、4 層のデータ構造を用意しておき、それらを用いて（各々が定数時間の計算をして）答えを返すのは \(\Theta(1)\) 時間アルゴリズムですが、一発で答えを出しているとは言えなさそうです。
\(O(1)\) とは定数のことである
上記の \(\Theta(1)\) でも触れましたが、それとは別に、\(O(1/n^2)\) のような集合もあります。
実際、「\(O(n)\) 時間かかる処理が発生する回数の期待値が \(O(1/n^2)\) 回で、〜」といった解析をする状況もあります*28。
もちろん、計算量が定数であるようなときに「\(O(1)\) 時間です」と主張するのは（上から抑えているだけなので）問題ありません。これを混同してしまうと困るかもしれません。
このソースコードの計算量は \(\Theta(n)\) 時間であり効率が悪い
たとえば、\(1\) 以上 \(n\) 以下の整数の総和を求める関数を書いたとします。
int sum(int n) {
int res = 0;
for (int i = 1; i <= n; ++i) res += i;
return res;
}
これは、Clang でコンパイルするとループのない形に最適化されます。
godbolt.org
アセンブリの解説はここでは割愛しますが、\(1+2+\dots+n = \frac{n(n+1)}{2}\) を用いた最適化をしているということですね。
なので、より厳密には（特に効率が悪いと主張する際には）、ソースコードで議論するのが正しくないケースもあります。
多くの場合はコンパイラちゃんがオーダーを改善してくれることはない気もするので問題なさそうですが、「コンパイラちゃんはオーダーの最適化をしない」という思い込みはよくないかもしれないねということです*29。
「コンパイラちゃんはオーダーを悪化させない」という思い込みをしているという指摘もあります。悪化させないでほしいです。
\(\log(n)\) は定数・\(\alpha(n)\) は現実的な範囲で 5 以下程度なので定数
\(\alpha(n)\) は inverse Ackermann function と呼ばれる、増加が非常に遅い関数です。
半ばギャグで言われているとも思います*30が、定数では、ないじゃん。
とはいえ、\(\log(n)\) や \(\alpha(n)\) は \(n\) と比べて非常に遅く増加するのは事実です。
そのための記法として、soft-O 記法というのがあります。\(f(n)=\widetilde{O}(g(n))\) は、ある \(k\) に対して \(f(n)=O(g(n)\log(g(n))^k)\) となることを意味します。
特に、\(O(n\log(n)\log(\log(n)))\) のような log が煩雑になるものや、その煩雑な部分の詳細な解析が難しいとき（あるいは本質的に議論したいのはそこではないとき）などに、\(\widetilde{O}(n)\) のように書かれたりします。
同様に、\(2^n\) に対して \(n\) の多項式は十分小さいので、そうした項を陽に考慮したくないときもあります。
そうしたときに、\(n\) の多項式を \(\poly(n)\) と書くことがあります。\(n^{O(1)}\) の意味だと思います*31。
\(O(2^n\cdot \poly(n))\) のように使います。
また、\(\log(n)\) の多項式を \(\polylog(n)\) と書くこともあります。\(n\cdot\log(n)\log(\log(n))\in O(n\cdot\polylog(n))=\widetilde{O}(n)\) のような感じです。
ところで、\(\alpha\) は競プロ界隈ではあまり知られていない感があったので、調べて記事を書きました。
rsk0315.hatenablog.com
\(64\) 倍高速化したので \(O(n/64)\)、\(10^{10}\) 回の演算をするので \(O(10^{10})\) など
定数倍は無視するので、それぞれ \(O(n)\), \(O(1)\) と同じ意味です。
記法としては、10000 倍効率を悪くしても \(O(n/64)\) と書けるし、1 回しか演算しなくても \(O(10^{10})\) と書けます。書く意味はないですけど...
それはそれとして、表現したいことに対して記法が不適切そうです。
\(64\) 倍高速化した場合は、「元の計算量を \(T(n)\) として \(\frac{1}{64}T(n)\) になった」とか言うのもアリな気もします？*32
また、実際に \(10^{10}\) 回の演算回数であることを知っているのなら、\(O\) を使う必要はないですね。
この誤用が出てくる文脈は、「入力としてありうる \(n\) の最大値は \(10^5\) で、\(O(n^2)\) の計算量なので、\(n=10^5\) を代入して \(O(10^{10})\)」のようなびっくり用法*33なのですが、不勉強な人にとっては自然に見えるらしいです？
なお、当然、\(n\) がどれだけ増えても定数回の計算で済むのであれば、\(O(10^{10})\) と書いても正しいです。\(O(1)\) と書けばいいですけど、自由なので。
ところで、bool の配列各々に対して論理演算を行う代わりに 64 bit 整数を用いて 64 個の bit をビット演算で並列に処理するのを 64 倍（定数倍）高速化と言うのは妥当か？という疑問があり、それに関する 記事 も書きました。実は \(\log(n)\) 倍の高速化という見方ができそうです。
このアルゴリズムもそのアルゴリズムも \(\Theta(n)\) 時間なので計算量は同じ・ループ回数を半分にしたけど計算量は同じ、など
実際の計算量と、そのオーダーは別物です。「オーダーは同じ」くらいの言い方が妥当でしょうね。
オーダーで言えば、「1 回マージソートを行う」も「シャッフルしてからマージソートを行うのを 500 万回繰り返す」も同じ見た目になってしまいますが、これらの計算量（オーダーのことではなくコストの総和）は異なりますね。
「ある \(\varepsilon\gt 0\) が存在して \(O(n^{2-\varepsilon})\) 時間で解ける」を
「\(o(n^2)\) 時間で解ける」と言い換えてしまう
これらは同値ではないです。
たとえば、\(\Theta(n^2/\log(n))\) 時間で解いたとします。これは、\(o(n^2)\) 時間で解いたことにはなりますが、\(n^2/\log(n)\in O(n^{2-\varepsilon})\) なる \(\varepsilon\gt 0\) は存在しません。
たとえば \(n^{1.99999999}\) よりも \(n^2/\log(n)\) の方が増加度合いが大きいです。
\(\varepsilon\) をどれだけ小さくしても、\(n\) が十分大きくなると \(n^2/\log(n)\) の方が大きくなってしまうため、\(n^{2-\varepsilon}\) 時間で解いたことにはならないわけですね。
\(2^{\Theta(n)} = \Theta(2^n)\)
たとえば、\(2n\in\Theta(n)\) を左辺に代入すると、\(4^n\) になりますが、これは \(\Theta(2^n)\) ではありません。
同様に \(2^{o(n)}\neq o(2^n)\) が成り立ちますが、これの証明となるような関数を挙げてみてください。
\(2n\notin o(n)\) なので、上記の例をそのまま使うことはできないことに注意してください。
宛先はこちらです*34：
\(\phi(n)\) は \(O(\sqrt{n})\)
これは誤用というよりは省略されているだけ*35という気もしますが、一応触れておきます。
Euler の totient 関数と呼ばれる関数 \(\phi(n)\) があります。
これは競技プログラミングなどでは比較的頻繁に出てくるのですが、たとえば各 \(n\) に対して \(\phi(2^{n}) = 2^{n-1}\) となるので、\(\phi(n)\in O(\sqrt{n})\) とはなりません。
それはそれとして、素朴な方法でこの値を求めるアルゴリズムは \(O(\sqrt{n})\) 時間かかるので、それを指してこのような言い方が（特に口語的な文脈では）なされるときもあるわけですね*36。
任意の \(f(n)\) と \(g(n)\) に対して、\(f(n)\in(O(g(n))\cup\Omega(g(n)))\) となる
これはもしかすると意外かもなのですが、成り立ちません。
\(g(n)\) がまともな関数とは限らないからですね。
\(f(n) = n\), \(g(n) = n^{1+\sin(n)}\) などの例では、\(g(n)\) が \(n^0\) くらい小さくなったり \(n^2\) くらい大きくなったりしてしまいます。
十分大きい \(n\) に対しても \(g(n)\) の定数倍が常に \(f(n)\) 以下になったり、あるいは常に \(f(n)\) 以上になったりはしてくれないわけです。
もっとふざけた例として、\(f(n)\) は「\(n\) が奇数なら \(\log(n)\)、偶数なら \(2^{n}\)」、\(g(n)\) は「\(n\) が奇数なら \(2^{n}\)、偶数なら \(\log(n)\)」なども挙げられます。
\(n+1\in O(n)\) や \(2^{n+1}\in O(2^n)\) なので当然 \( (n+1)!\in O(n!)\)
\( (n+1)! \ge n\cdot n!\) なので、\( (n+1)!\) は \(n!\) より \(n\) ひとつぶん速く増加してしまいますね。よって成り立ちません。
直感的なイメージとしては、「\(n\) や \(2^n\) のような発散が遅い関数では \(1\) 増えたところで差は無視できるが、\(n^n\) のように速い関数ではそうではない」といった感じだと思います。
同様に、たとえば \(O(n^{\log_3(4)})\ne O(n^{\log_2(3)})\) です。
\(\Theta(\log(n^2))\) から \(\Theta(\log(n))\) にオーダーを改善した
\(\log(n^2) = 2\log(n)\) であり、定数倍の違いしかないので、オーダーは改善されていません。
「\(10^5\) のオーダー」などの言い回し
「だいたい 6 桁程度の大きさ」のような文脈で使われがちな「オーダー」とは意味合いが異なります。
big-O はそうした文脈のための記号ではないので、\(O(10^5)\) などと書くのはナンセンスです。
「だいたい \(10^5\)」のような文脈では「\(\sim 10^5\)」のような書き方の方が妥当に見える気がします。
計算量の見積もりに関して
長かったですが、実用的に計算量を見積もるための方法の話です*37。
上記の部分は、よくある誤解をしてほしくないがために書いた部分です。
一番最初のソートの計算量見積もりでやったように、定数倍に関する情報を捨ててしまうことが多いです（正確に見積もるのも困難な上、そこまで見積もるメリットもないことが多いので）。
その前提では、各行にいちいちコスト \(c_i\) などを割り当てたりせず、
- for \(i\) in \(1, \dots, n\)
のように簡略化して、「\(\Theta(1)\) 時間の処理を \(n\) 回やるので \(\Theta(n)\) 時間」と言ってしまってよいでしょう。
ここで \(\Theta(1)\) 時間の処理と言っているのは、四則演算やビット演算、配列へのアクセス、\(\Theta(1)\) 時間で終わることがわかっている関数の呼び出しなどです。
関数呼び出しであっても、長さ \(n\) の配列をコピーして引数として渡すとか、関数の内部で \(\omega(1)\) 時間の処理をしているとか、そういったものはだめです*38。
また、2 重ループであっても、
- for \(i\) in \(1, \dots, n\)
- for \(j\) in \(1, \dots, n\)
とかであれば、
- for \(i\) in \(1, \dots, n\)
となり、「\(\Theta(n)\) 時間の処理を \(n\) 回やるので \(\Theta(n^2)\) 時間」と言えます。
内側のループの範囲が \(1, \dots, i\) だとしても、同様に \(\Theta(n^2)\) 時間になります。\(\sum_{i=1}^n i = \Theta(n^2)\) だからですね。
ループが何重になっても、各ループの範囲が \(n\) だったり外側のループで固定した値（上の例で言うところの \(i\)）であれば、\(\Theta(n^{\bullet})\) の形になります。
なお、ループの途中で break や continue があったりする場合は、条件に応じて個別に解析する必要があります。
2 重ループでも、ループごとの範囲が特殊な形の場合は、\(o(n^2)\) になるケースもあります。
- for \(i\) in \(1, \dots, n\)
- for \(j\) in \(1, \dots, \lfloor n/i\rfloor\)
これは、\(O(\sum_{i=1}^n \frac{n}{i})\) 時間となりますが、
\[
\begin{aligned}
\sum_{i=1}^n \frac{n}{i} &= n\cdot\sum_{i=1}^n \frac{1}{i} \\
&= n\cdot \left(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n}\right) \\
&\le n\cdot (1+\log_e(n)) \\
\end{aligned}
\]
となることが知られており、\(O(n\log(n))\) 時間となります*39。
界隈では、「調和級数*40で log になるやつ」などの愛称（）で親しまれています。
他にも、自明でない計算量解析は多々ありますが、ここでは割愛します*41。
また、ここでは詳細を省きますが、vector・set・list・heap などに代表されるデータ構造の各操作は \(O(1)\) 時間で行えないものもあります。そうしたもの、たとえば 1 回あたり \(\Theta(\log(n))\) 時間かかるものは、\(n\) 回実行すると \(\Theta(n\log(n))\) 時間になりますね。
あるいは、string 同士の値が等しいかどうかの比較も最悪時は \(O(1)\) 時間ではできませんね。
雑談
各データ構造がどれだけの時間を要するかについて、もしかすると計算量の表を丸暗記しようとしている人もいるのかもしれませんが、それらがどういう構造でデータを管理しているのかを知ると、自然に覚えられる気がします。
言語によっては list.contains(x) とか set.find { isEven(x) } とか記述できたりしてしまいますが、内部でループしているので最悪時 \(\Omega(n)\) 時間になってしまいますね。高速にそれらを求めたい状況で初心者がうっかりそれらのメソッドを使ってしまうのを防ぐため、list.iKnowThatAListTakesLinearTimeToTestWhetherItContainsTheValueButIReallyWantToDoIt(x) などの名前にするべきという意見（）もあります*42。
元ネタ：
ここまでしなくても、コストが大きいメソッドは list.contains$(x) みたいに $ をつけさせるとかの設計は十分アリなような気もします。何をもってコストが大きいとするかで議論がありそうですが。コストがさらに大きいときは $$ のように増えていくとかも面白そうですね。
たとえば、
res = 0;
for$$ i in 0..n {
for$$ j in 0..n {
if set.contains$(i + j) {
res += 1;
}
}
}
のように書き、for$$ ふたつと set.contains$ ひとつを合わせてコストは合計 $ 5 つ分とする（ネストされている部分について $ を合計する）（各ネストに対してそれを行い、その最大値をプログラム全体のコストと見積もる）、のようなデザインの言語があっても面白そうな気がします。
もちろん break とかがあるとうまくいかなくなるので、上記の案はまだまだですが。
特に競技プログラミングの文脈においては、\(n\) の上限と実行制限時間が与えられ、その時間に間に合うコードを書くのが主です。
この \(n\) の上限値が（注目しているアルゴリズムの計算量の見積もりに関して）十分大きいとは言えないときは、必ずしもオーダーによる議論が役に立たないこともありえそうです。
また、除算などコストの重い処理をたくさん行う場合と、加算などの軽い処理を同じ回数行う場合を比べると、実行時間にそれなりに大きい差が出ることが予想されます。
こうした場合に、定数倍を無視して議論すると（競技プログラミングはオーダーではなく実行時間制限に対してうまくやる必要があるので）失敗することがあります。
「除算を \(2n+o(n)\) 回、それ以外の処理を \(O(n)\) 回」とか見積もるといいのかなぁ*43。
なんにせよ、競技プログラミングと（上記の意味で）相性のよい計算量見積もりの記法は、おそらくないのが現状です。
多くの場合はオーダーで事足りるので問題ないですが、定数倍や非支配項が重いものを見積もりたいときはちょっと困ります。
すばらしい記法を提案すれば、たぶん人気者になれると思います。
実際の計算時間の見積もり
オーダーだけ見積もって、巷で言われているように「\(n\) が \(10^5\) くらいになりうるなら \(\Theta(n^2)\) 時間のアルゴリズムは 2 秒には収まらないだろうな〜*44」とか、「\(n\) が \(10^5\) くらいなら、\(O(n\log(n)^2)\) はまぁ 2 秒に収まるだろうな〜」といった推測をすることは少なくはないです。
実際、（\(O\) などの記法が保証してくれる事実ではないにせよ）\(O(f(n))\) の \(f(n)\) に入力の \(n\) の最大値を代入して計算した値が \(10^8\) 程度以下なら 2 秒に間に合うだろうなぁといった見積もりをして大きく外さないことは多いです。
が、\(O\) 自体がこうした用途のための記法ではないことは留意しておいた方がよさそうです。
定数倍がめちゃくちゃ大きいアルゴリズムというのは存在して、たとえば \(2^{65536}\) とか、それよりも大きいようなアルゴリズムもあるらしいです*45。普段はそうしたアルゴリズムを作らないはずなので、\(O\) の定数倍があまり大きくないだろうという暗黙の了解みたいなのがあってしまっているわけですね。
いろいろな計算量
上記では、最良計算量と最悪計算量について紹介しましたが、他にも 平均計算量 (average complexity)、償却計算量・ならし計算量 (amortized complexity)、期待計算量 (expected complexity) と呼ばれる概念もあります。
概要だけ説明すると、次の通りです。
- 平均計算量
- サイズ \(n\) の入力すべてに対しての計算量を考え、その平均を表す。
- 最悪計算量は \(\Theta(n^2)\) だが、多くのケースでは \(O(n\log(n))\) であり、平均すると \(O(n\log(n))\) という例がある。
- 償却計算量
- データ構造への操作は、毎回同じオーダーの時間がかかるとは限らない。
- 各操作における計算量を平均したもの。
- 多くの状況では時間があまりかからないが、たまに時間がかかるといったことはよくある。
- 領域を再確保するとかね。
- 最悪ケースは \(\Theta(n)\) かかるが、平均すると操作一つあたり \(O(1)\) ということはよくある。
- 期待計算量
- 乱数を用いるアルゴリズムもよくある。
- 乱数の値によって計算量が変わることはよくあるが、その期待値（確率の重みつき平均）。
これらは各々平均に関するものですが、何に関する平均なのかが異なるので、言葉を使う際には注意が必要です。
たとえば、償却計算量のつもりで平均計算量と言ってしまうと齟齬が生じます。
平均計算量は「入力によっては遅くなるケースもあるかも」という見積もりなのに対し、償却計算量はそういう話ではないので、競プロにおいては後者の見積もりの方がうれしいです。
もちろん最悪計算量を見積もれればそれに越したことはないですが、償却計算量で見積もっても損することはなさそうです。
こちらの記事が詳しいです。
noshi91.hatenablog.com
いろいろな計算モデル
上記では、四則演算が \(\Theta(1)\) 時間でできるという仮定をしていましたが、これはちょっと怪しいです。
たとえば、メモリにギリギリ乗るような整数（16 GB = 237 bits、\(2^{2^{37}} = 2^{137438953472}\)、41373247568 桁）に関する四則演算が、ワードひとつぶん（64 bits、\(2^{64}\)、20 桁）と同じ時間でできるという仮定は強すぎ・非現実的です。
そこで、ワードの大きさも計算量に考慮したモデルとして、word RAM というモデルがあります（上記のワードサイズを考慮しないものは RAM と呼ばれるモデルに近そうです）。
他にも、実行できる演算の種類が異なるメジャーなモデルがいくつかあります。
除算は重いので定数時間の命令セットには含めないとする立場もあるらしいです？*46
word RAM についてはこの記事で触れました。
rsk0315.hatenablog.com
回路（AND や OR などのゲートがある）とかを用いるモデルもあります。チューリング機械とかもありますね。
競技プログラミングの文脈でこれらが出てくることはあまりなさそうですが、おもしろいと感じる人にはおもしろそうな分野だと思います。
ざっくり、以下のようなイメージの機械です（自分と呼んでいるのが機械ちゃんです）。
- 無限に長く続くマス目があり、各マス目には記号が書かれている。
- 最初、自分は「開始マス」におり、「初期状態」という状態であるとする。
- 今いるマスに書かれた記号と自分の状態に応じて以下の処理を行う。
- 自分の状態を更新する（同じ状態のままでもよい）。
- 今いるマスの記号を更新する（同じ記号を書いてもよい）。
- 左右どちらか隣に移動するか、その場に留まる。
- 「終了状態」になったら終了
- そのときマス目たちに書かれた記号列を出力と見なす。
これだけの操作で、我々が普段使っているようなプログラミング言語と同等の問題を解けるらしいです。
いろいろなパラメータ
上記では入力サイズ \(n\) に関しての関数で記述しましたが、出力に関する値や、入力に含まれる値の最大値、その他何らかの値（入力の整数が持つ素因数の種類数、入力のグラフが持つパラメータ）など、見積もりのために使えるのであれば、それらを使ってしまってよいです。
特に、出力に関する値（「条件を満たすものをすべて出力してね」といった問題における出力の個数など）で計算量が抑えられるアルゴリズムは、output-sensitive algorithm と呼ばれたりしています。
ソートの計算量に関して
発展的な内容です。適宜調べながら読むなり、知識をつけてから読み直すなり、強い人に聞きながら読むなりしてもらえたらうれしいかもです。
最初に紹介したソートアルゴリズム 1 では区間の最小値を順に求めていきました。
賢明な読者はお気づきの通り、これはセグ木で高速化できます。よって、\(O(n\log(n))\) 時間にできます。
ところで、大小比較に基づくソートアルゴリズムは worst \(\Omega(n\log(n))\) 時間かかることが知られています。
長さ \(n\) の順列は \(n!\) 通りありますが、一回の大小比較では半分程度に絞り込むことしかできないので、\(\log_2(n!)\) 回程度の比較が必要になります。\(\log_2(n!)\in\Theta(n\log(n))\) であるので、そうなります*47。
\(\log_2(n!)\in\Theta(n\log(n))\) に関して（クリックして展開）
Stirling の近似公式を使えば済むと言う人もいるし、Stirling の近似公式を使わなくても済むと言う人もいます。
大道具を使ってすぐ終わらせる方が楽か、大道具を使わずに済ませる方が楽かみたいな話ですね。
前者であれば公式を調べればすぐ終わるので、ここでは後者を紹介してみます。
なお、ソートの話に関して言うためには \(\log_2(n!)\in\Omega(n\log(n))\) さえ言えばよいですが、\(O(n\log(n))\) の方もついでに示します。
まず、自明に \(n! \le n^n\) なので、両辺に log を適用して \(\log(n!)\le n\log(n)\) です。よって \(\log(n!)\in O(n\log(n))\) です。
ここからすごいのですが、たとえば、\(6!\ge 6\cdot 5\cdot 4\ge 3\cdot 3\cdot 3 = (6/2)^{6/2}\) や \(7!\ge 7\cdot 6\cdot 5\cdot 4\ge 3\cdot 3\cdot 3 = \floor{7/2}^{\floor{7/2}}\) のようなものを考えてください。
\[
\begin{aligned}
n! &\ge \frac{n!}{\lfloor n/2\rfloor !} \\
&\ge \lfloor n/2\rfloor^{\lfloor n/2\rfloor}
\end{aligned}
\]
よって、log を適用して \(\log(n!)\ge \lfloor n/2\rfloor\log(\lfloor n/2\rfloor)\) を得ます。
すなわち \(\log(n!)\in\Omega(n\log(n))\) です。
以上より、\(\log(n!)\in\Theta(n\log(n))\) です。
（クリックして展開部分おわり）
というわけで、区間最小値を求める操作と・値の更新をする操作を両方 \(o(\log(n))\) 時間でできてしまうデータ構造を思いついてしまった場合、自分の勘違いを疑うのが賢明です*48。
よくある：
このように、解けない問題を知っていると、「自分が思いついてしまったデータ構造を使うと、解けないことが証明されている問題を解けてしまう。よって自分が勘違いをしているはずだ」と気づくことができる場合があります*49。
あるいは、「この予想が正しいとすると、その問題は \(O(n^{2-\varepsilon})\) では解けないことが知られている」といった形式の事実もあります。
そうした問題を \(O(n^{2-\varepsilon})\) で解けば、その予想が正しくないと証明したことになるわけですね。
コメント返信
イマジナリーコメントに対して返信しておきます。
「\(O\) がサンドイッチの記法ではないことはわかったが、（なんらかの理由で）サンドイッチの記法として \(O\) を使い続けるぜ！」というコメントが多かったです。
正直、わざわざ誤用を続けたい気持ちはわかりませんが、宗派が違いそうなので特に諭す気はしません。
それはそれとして、O を入力する手間と比べて Ω や Θ を入力するのが面倒すぎるという問題はあります。
mac であれば、option + z*50 で Ω が入力できます*51が、それでもやや面倒です。
正しさに固執しない人にとっては無視できないコストだと言われても納得してしまいます。
とりあえずはちゃんと理解して、正しく書けと言われたら書けるくらいになってくれたらうれしいです。
（追記）案の定たくさんの人の目に触れてしまい、多くのコメントをいただいてしまいました。温かいコメントから心ないコメントまでたくさんありました、ありがとうございます。
「こんなの知る必要がない」という旨のコメントと「こんなの学部で CS やってればみんな知ってる*52」という旨のコメントが両方ついており、人には人の常識だなぁと思いました。
参考文献
- Introduction to Algorithms
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.
- 日本語版 もあります。
- 特に、計算量の話については試し読みができます、すごいね
ちゃんとした記事は他にもあります。
torus711.hatenablog.com
あとがき
当初の予定より書きたいことがたくさん増えてしまって、（数式部分の TeX なども含めると）44k 文字を超えてしまいました。
読んでいる方も疲れているでしょうが、書いている人も疲れています。
ここまで読んでもらえていたらうれしいです、ありがとうございます。
（これは言及するか迷ったのですが）図らずも Twitter で計算量の話が流行ってしまっています。
すでに「もう誰も計算量の話してない」の状態になっているかもですが、話題に乗ろうとして書いた記事でないことは主張したいです*53。
この時点から 7k 文字くらい増えていますが...
おわり
おわりです。
お疲れさまですにゃ。
