えびちゃんの日記

えびちゃん(競プロ)の日記です。

できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事

計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。

数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。

それから、この記事が自分には合わないな〜と思ったときは、(別の記事を 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 は次の通りです。

  1. for \(i\) in \(1, \dots, n-1\)
    1. // \( (a_i, \dots, a_n)\) の最小値を探し、\(a_i\) と交換する。
    2. \(i' \gets i\) // 今まで見た最小値の添字
    3. for \(j\) in \(i+1, \dots, n\)
      1. if \(a_{i'} \gt a_j\)
        1. \(i' \gets j\)
    4. \(x \gets a_i\)
    5. \(a_i \gets a_{i'}\)
    6. \(a_{i'} \gets x\)

アルゴリズム 2 は次の通りです。

  1. for \(j\) in \(2, \dots, n\)
    1. \(x \gets a_j\)
    2. \(i \gets j-1\)
    3. // \( (a_1, \dots, a_{j-1})\) がソート済み。適切な位置に挿入する。
    4. while \(i\ge 1\) and \(a_i \ge x\)
      1. \(a_{i+1} \gets a_i\)
      2. \(i \gets i-1\)
    5. \(a_i \gets x\)

アルゴリズム 3 は次の通りです。

  1. 長さ \(n\) の未初期化の配列 \( (b_1, \dots, b_n)\) を用意する
  2. for \(e\) in \(1, \dots, \infty\)
    1. \(l \gets 2^e\)
    2. // 長さ \(l/2\) の隣り合うソート列から長さ \(l\) のソート列を作る
    3. for \(i\) in \(0, \dots, \lceil n/l\rceil-1\)
      1. \(i_l \gets i\cdot l\)
      2. \(i_r \gets \min\{n, i_l+l/2\}\)
      3. \(e_l \gets i_r\)
      4. \(e_r \gets \min\{n, i_l+l\}\)
      5. \(j \gets i_l\)
      6. while \(i_l \lt e_l\) and \(i_r \lt e_r\)
        1. if \(a_{i_l} \lt a_{i_r}\)
          1. \(b_j \gets a_{i_l}\)
          2. \(i_l \gets i_l+1\)
        2. else
          1. \(b_j \gets a_{i_r}\)
          2. \(i_r \gets i_r+1\)
        3. \(j \gets j+1\)
      7. for \(i'\) in \(i_l, \dots, e_l -1\)
        1. \(b_{j+i'-i_l} \gets a_{i'}\)
      8. for \(i'\) in \(i_r, \dots, e_r-1\)
        1. \(b_{j+i'-i_r} \gets a_{i'}\)
      9. for \(i'\) in \(i\cdot l, \dots, e_r-1\)
        1. \(a_{i'} \gets b_{i'}\)
    4. if \(l \ge n\)
      1. 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

そこで、各行に対して「それを実行するための時間」と「その実行回数」の積を求め、その合計をそのアルゴリズムの時間計算量と呼ぶことにします。 時間計算量が小さいほど最も早く終了することになります。

各行を実行するための時間は、演算の種類や(現実に即して言えば)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^2+3n\in\Theta(n^2)\)

ある \(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^2\notin\Theta(n^3)\)

いかなる \(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\) を入れた」のような認識にはならないでほしいです。

自分は「計算量は \(O(n^2)\) である」と言ったとき、「1+1 は 2 である」のように値を示しているのではなく、「1+1 は偶数である」のように性質を示しているという認識をしている気がします。オーダーが \(n^2\) であるというのが、その計算量の性質に対応するわけですね。

また、たとえば C++ の関数の規格では、次のような表現がよく出てきます。

Complexity: \(O(n\log(n))\) comparisons

比較演算以外については特に言及していませんが、比較の回数が全体のボトルネックになるので、その回数が \(O(n\log(n))\) 回だと言っているという背景があると思います*16

比較が \(O(1)\) 時間ではない class を引数とする場合のことを気にして \(O(n\log(n))\) と書いていないという見方もあると思います。

\(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)\in 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)\) 時間かかってしまいそうです。 なお、たとえば \(O(n^{0.75}/\log(n))\) 時間のアルゴリズムも存在します。

rsk0315.hatenablog.com

(クリックして展開部分おわり)

またコピペですが、以下が成り立つとき、\(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\) については、計算機科学以外ではこれと異なる定義が用いられるようなので、注意が必要かもしれません。

\(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} \]

証明(クリックして展開)

  • \(n^2 \in o(n^3)\)

任意の \(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\) とすればよい。

  • \(n^2+3n \notin o(n^2)\)

ある \(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))\) に関しても、定数倍でサンドイッチできると言っているだけで、比例するとは言っていません。 (非支配項を無視すれば比例すると言っていい気もするので、目くじらを立てすぎかもですが、正確ではない気がします)

これ明らかに嘘で、\(f(n)\) を「\(n\) が偶数なら \(2n\)、奇数なら \(3n\)」などが反例としてあります。私が悪かったです(ぺこり)。

さておき、界隈では、\(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)\) となることを意味します。

\(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)\) になった」とか言うのもアリな気もします?*31

また、実際に \(10^{10}\) 回の演算回数であることを知っているのなら、\(O\) を使う必要はないですね。 この誤用が出てくる文脈は、「入力としてありうる \(n\) の最大値は \(10^5\) で、\(O(n^2)\) の計算量なので、\(n=10^5\) を代入して \(O(10^{10})\)」のようなびっくり用法*32なのですが、不勉強な人にとっては自然に見えるらしいです?

なお、当然、\(n\) がどれだけ増えても定数回の計算で済むのであれば、\(O(10^{10})\) と書いても正しいです。\(O(1)\) と書けばいいですけど、自由なので。

ところで、bool の配列各々に対して論理演算を行う代わりに 64 bit 整数を用いて 64 個の bit をビット演算で並列に処理するのを 64 倍(定数倍)高速化と言うのは妥当か?という疑問があり、それに関する 記事 も書きました。

このアルゴリズムもそのアルゴリズムも \(\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)\) なので、上記の例をそのまま使うことはできないことに注意してください。

宛先はこちらです*33

\(\phi(n)\) は \(O(\sqrt{n})\)

これは誤用というよりは省略されているだけ*34という気もしますが、一応触れておきます。

Euler の totient 関数と呼ばれる関数 \(\phi(n)\) があります。 これは競技プログラミングなどでは比較的頻繁に出てくるのですが、たとえば各 \(n\) に対して \(\phi(2^{n}) = 2^{n-1}\) となるので、\(\phi(n)\in O(\sqrt{n})\) とはなりません。

それはそれとして、素朴な方法でこの値を求めるアルゴリズムは \(O(\sqrt{n})\) 時間かかるので、それを指してこのような言い方が(特に口語的な文脈では)なされるときもあるわけですね*35

任意の \(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\) ひとつぶん速く増加してしまいますね。

\(\Theta(\log(n^2))\) から \(\Theta(\log(n))\) にオーダーを改善した

\(\log(n^2) = 2\log(n)\) であり、定数倍の違いしかないので、オーダーは改善されていません。

計算量の見積もりに関して

長かったですが、実用的に計算量を見積もるための方法の話です*36。 上記の部分は、よくある誤解をしてほしくないがために書いた部分です。

一番最初のソートの計算量見積もりでやったように、定数倍に関する情報を捨ててしまうことが多いです(正確に見積もるのも困難な上、そこまで見積もるメリットもないことが多いので)。

その前提では、各行にいちいちコスト \(c_i\) などを割り当てたりせず、

  • for \(i\) in \(1, \dots, n\)
    • \(\Theta(1)\) 時間の処理

のように簡略化して、「\(\Theta(1)\) 時間の処理を \(n\) 回やるので \(\Theta(n)\) 時間」と言ってしまってよいでしょう。

ここで \(\Theta(1)\) 時間の処理と言っているのは、四則演算やビット演算、配列へのアクセス、\(\Theta(1)\) 時間で終わることがわかっている関数の呼び出しなどです。 関数呼び出しであっても、長さ \(n\) の配列をコピーして引数として渡すとか、関数の内部で \(\omega(1)\) 時間の処理をしているとか、そういったものはだめです*37

また、2 重ループであっても、

  • for \(i\) in \(1, \dots, n\)
    • for \(j\) in \(1, \dots, n\)
      • \(\Theta(1)\) 時間の処理

とかであれば、

  • for \(i\) in \(1, \dots, n\)
    • \(\Theta(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})\) の形になります。 なお、ループの途中で breakcontinue があったりする場合は、条件に応じて個別に解析する必要があります。

2 重ループでも、ループごとの範囲が特殊な形の場合は、\(o(n^2)\) になるケースもあります。

  • for \(i\) in \(1, \dots, n\)
    • for \(j\) in \(1, \dots, \lfloor n/i\rfloor\)
      • \(O(1)\) 時間の処理

これは、\(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))\) 時間となります*38。 界隈では、「調和級数*39で log になるやつ」などの愛称()で親しまれています。

他にも、自明でない計算量解析は多々ありますが、ここでは割愛します*40

また、ここでは詳細を省きますが、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) などの名前にするべきという意見()もあります*41

元ネタ:

ここまでしなくても、コストが大きいメソッドは 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)\) 回」とか見積もるといいのかなぁ*42

なんにせよ、競技プログラミングと(上記の意味で)相性のよい計算量見積もりの記法は、おそらくないのが現状です。 多くの場合はオーダーで事足りるので問題ないですが、定数倍や非支配項が重いものを見積もりたいときはちょっと困ります。

すばらしい記法を提案すれば、たぶん人気者になれると思います。

実際の計算時間の見積もり

オーダーだけ見積もって、巷で言われているように「\(n\) が \(10^5\) くらいになりうるなら \(\Theta(n^2)\) 時間のアルゴリズムは 2 秒には収まらないだろうな〜*43」とか、「\(n\) が \(10^5\) くらいなら、\(O(n\log(n)^2)\) はまぁ 2 秒に収まるだろうな〜」といった推測をすることは少なくはないです。

実際、(\(O\) などの記法が保証してくれる事実ではないにせよ)\(O(f(n))\) の \(f(n)\) に入力の \(n\) の最大値を代入して計算した値が \(10^8\) 程度以下なら 2 秒に間に合うだろうなぁといった見積もりをして大きく外さないことは多いです。 が、\(O\) 自体がこうした用途のための記法ではないことは留意しておいた方がよさそうです。

定数倍がめちゃくちゃ大きいアルゴリズムというのは存在して、たとえば \(2^{65536}\) とか、それよりも大きいようなアルゴリズムもあるらしいです*44。普段はそうしたアルゴリズムを作らないはずなので、\(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 と呼ばれるモデルに近そうです)。 他にも、実行できる演算の種類が異なるメジャーなモデルがいくつかあります。 除算は重いので定数時間の命令セットには含めないとする立場もあるらしいです?*45

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))\) であるので、そうなります*46

\(\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}\) のようなものを考えてください。 \[ \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))\) 時間でできてしまうデータ構造を思いついてしまった場合、自分の勘違いを疑うのが賢明です*47

よくある:

このように、解けない問題を知っていると、「自分が思いついてしまったデータ構造を使うと、解けないことが証明されている問題を解けてしまう。よって自分が勘違いをしているはずだ」と気づくことができる場合があります*48

あるいは、「この予想が正しいとすると、その問題は \(O(n^{2-\varepsilon})\) では解けないことが知られている」といった形式の事実もあります。 そうした問題を \(O(n^{2-\varepsilon})\) で解けば、その予想が正しくないと証明したことになるわけですね。

コメント返信

イマジナリーコメントに対して返信しておきます。

「\(O\) がサンドイッチの記法ではないことはわかったが、(なんらかの理由で)サンドイッチの記法として \(O\) を使い続けるぜ!」というコメントが多かったです。 正直、わざわざ誤用を続けたい気持ちはわかりませんが、宗派が違いそうなので特に諭す気はしません。

それはそれとして、O を入力する手間と比べて Ω や Θ を入力するのが面倒すぎるという問題はあります。 mac であれば、option + z*49 で Ω が入力できます*50が、それでもやや面倒です。 正しさに固執しない人にとっては無視できないコストだと言われても納得してしまいます。

とりあえずはちゃんと理解して、正しく書けと言われたら書けるくらいになってくれたらうれしいです。

(追記)案の定たくさんの人の目に触れてしまい、多くのコメントをいただいてしまいました。温かいコメントから心ないコメントまでたくさんありました、ありがとうございます。

「こんなの知る必要がない」という旨のコメントと「こんなの学部で CS やってればみんな知ってる*51」という旨のコメントが両方ついており、人には人の常識だなぁと思いました。

参考文献

  • Introduction to Algorithms
    • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.
    • 日本語版 もあります。
      • 特に、計算量の話については試し読みができます、すごいね

ちゃんとした記事は他にもあります。 torus711.hatenablog.com

あとがき

当初の予定より書きたいことがたくさん増えてしまって、(数式部分の TeX なども含めると)43k 文字を超えてしまいました。 読んでいる方も疲れているでしょうが、書いている人も疲れています。 ここまで読んでもらえていたらうれしいです、ありがとうございます。

(これは言及するか迷ったのですが)図らずも Twitter で計算量の話が流行ってしまっています。 すでに「もう誰も計算量の話してない」の状態になっているかもですが、話題に乗ろうとして書いた記事でないことは主張したいです*52

この時点から 6k 文字くらい増えていますが...

おわり

f:id:rsk0315:20211011031148p:plain

おわりです。

お疲れさまですにゃ。

f:id:rsk0315:20211012202447p:plain  

 

 

*1:お金に余裕がある人は購入してもよいです。

*2:実際、「計算量」でググった 1 ページの記事は怪しい記述が多く、泣き出してしまいました。

*3:短く教えてくれといった要望に応える気はありません。態度を改めてくれるとうれしいです。← と最初書いていたのですが、こちらにも問題があるくらいの長さになっている気もします。

*4:なんか「こんなの知る必要ない」みたいなコメントがいくつか見られたので補足しちゃいます。

*5:定義される前にこの記事を閉じてしまった場合は適宜思い出すなり、忘れたまま過ごすなりしてください。

*6:アルゴリズムとは、入力・出力が明確で、命令に曖昧性がなく、停止することが保証されている有限の命令列です。この例では配列 \(a\) が入力、それをソートしたものが出力です。

*7:「一番最初に書いてあったやつ」とかの基準であれば、わからなくても選べますが...

*8:実際には、キャッシュが効いたりして定数ではないこともあるでしょう。そこまでの考慮が必要なら、それに応じたモデルを考えた方がよさそうです。

*9:初心者的には \(\sum\) の計算がおぼつかないかもしれませんね。単なる総和なので、怯えずに適宜調べたりしてくれると助かります。

*10:した方が楽だな〜というだけで、必ずそうしなくてはいけないという意味ではないです。

*11:前者を主要項、後者を低次の項と呼んだりもします。

*12:ここで \(T_1(n)=O(n^2)\) では?と思った人は、正しく知っていない可能性が高いです。

*13:元の関数の増加度合いは、支配項の増加度合いと一致します。というか、元の関数の増加度合いの原因となっている項が支配項と言う方が正しそうです。なので、「支配項の増加度合いの改善」ではなく単に「オーダーの改善」と言ってよいです。

*14:係数や非支配項をいちいち求めるのが面倒な場合・それらが重要でない場合に使ったりします。

*15:「偶数個」とか「3 桁万円」とかも、ある偶数 \(n\) があって \(n\) 個とか、ある 3 桁の数 \(n\) があって \(n\) 万円といった意味合いですよね。

*16:ふざけた処理系においては、比較以外に無駄なことをしてめちゃくちゃな計算量にすることが許される?

*17:\(x\) に対してある \(y\) を使って \(x\le y\) や \(x\lt y\) を示すことを、\(x\) を(\(y\) で)上から抑えると言います。逆向きなら下から抑えると言います。

*18:文献によっては \(\mathrm{O}\) と書いたり \(\mathcal{O}\) と書いたりもします。意味は同じです。

*19:「高々〇〇」は「〇〇以下」と似たような意味です。at most 〇〇。

*20:\(S=T\) を含意するときに \(S\subset T\) と書き、そうでないときに \(S\subsetneq T\) などを使う宗派もあります。ここでは、前者に \(S\subseteq T\)、後者に \(S\subset T\) を使う宗派を採用しているつもりです。

*21:ありえるというか、そういう状況でないですよーというのを \(O\) では示せないということです。

*22:「\(x+\frac{1}{x}\) の最小値を求めてね」という問題で「相加相乗平均の公式から \(x+\frac{1}{x}\ge 2x\cdot\frac{1}{x}=2\)」という不等式だけ示して満足してしまうやつに似ています。実際に最小値 \(2\) をとる \(x\) の存在はこの不等式からは言えないですね。

*23:\(O\) を示すときに使った \(n_0\) と \(\Omega\) を示すために使った \(n_0\) の最大値を、\(\Theta\) を示すための \(n_0\) として使えばよさそうです。

*24:\(O\) のとき同様、\(\mathrm{o}\) と書く文献もあります。

*25:初心者向け:「任意の \(c_U\)」はあなたの任意で選んだ \(c_U\) ではなく、あなたの敵の任意で選んだ \(c_U\) といったような意味合いです。敵がどう \(c_U\) を選んでもあなたは \(n_0\) を見つける必要があります。

*26:理論が悪いのではなく、理論を適用させる状況が間違っているというよくあるやつな気もします。

*27:小さい文字で書いてあるいじわるな契約書っぽさを感じます。

*28:https://web.stanford.edu/class/archive/cs/cs166/cs166.1206/lectures/12/Slides12.pdf p.242

*29:コンパイラがオーダーを落としていることを知らずに手で修正したが速度が改善しなかった、という状況も考えられそうです。

*30:「\(\log(n)\) は定数だが \(\log(n)^2\) は定数ではない」「2 の定数乗は定数なので、\(n=2^{\log(n)}\) も当然定数」「セグ木の log は定数だが set の log は定数ではない」etc.

*31:正確に \(1/64\) の計算量になったという主張に見えるので、それはそれで怪しくも見えますが。

*32:一度定数倍を無視してから値に関する議論をするの、ナンセンスっぽい。

*33:当時、別であろうとは思っていたものの、例がパッと出てこず、このようなツイートをする運びとなってしまいました。

*34:うなぎ文であるという指摘もありました。

*35:私としてはあまり好きな使い方ではないですが、個人の感想なので。

*36:巷にある記事の \(O\) を \(\Theta\) に書き換えて似たような話をしているだけという見方もありそうです。

*37:引数の準備とか関数内部の処理とかは抜きにして「関数を呼ぶ」の自体は \(O(1)\) とする立場や、それら全部を含めて関数を呼んでいるという立場もありそうです。ここでの説明は後者ですね。

*38:\(\Omega\) を導入したあたりの例で言うところの「\(O(n^2)\) 時間であることはわかっていたが、天才視点では \(O(n\log(n) )\) 時間になっていた」という感じですね。

*39:\(\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{n}+\cdots\) の形の和を調和級数と呼びます。

*40:興味がある人向けキーワード:分割統治法の計算量(マスター定理)、部分集合列挙が \(O(3^n)\) になるやつ、二乗の木 DP など。初心者にすすめるには高度かも。

*41:linear time は、入力サイズ \(n\) に対して \Theta(n)\) 時間となること。日本語では線形時間と言います。

*42:これだと \(o(n)\) の定数倍が小さいことは保証していないですが、うーん、困りますね。

*43:口語では「10 の 5 で \(n^2\) はつらいだろ」くらいの言い方をしそうなものですが、フォーマルな言い方ではないですね。

*44:そういうのを galactic algorithm と呼ぶらしいです。

*45:Newton 法で定数回の乗算でできそうですが...? あるいは乗算も許さないのかも。

*46:ここふんわり議論。葉が順列に対応した二分木の高さの下限などを考えるといいと思います。

*47:永久機関完成したンゴwwww」ってやつですね。通じなかったら別にいいです。

*48:ここでは「ある時間以下では解けない」という例を示しましたが、いくら時間をかけても解けないことが知られている問題というのもあります。

*49:全然関係ないんですけど、⌥Z って洗濯表示にありそうな見た目してませんか? そうでもないか。

*50:日本語入力時は ω になるっぽい。

*51:これだと思っていたんですけど、そうでもないらしいです。どうして?

*52:逆張りオタクなので。

ロリハを知っている人のための接尾辞配列

最近ロリハあんまり人気なくない?

TL; DR

ロリハ + にぶたん で \(O(\log(n))\) 時間で大小比較できるので、愚直に比較する代わりにそれを使って \(O(n\log(n)^2)\) 時間で構築できる。

おさらい

ロリハ

ロリハ (rolling hash) のおさらいを軽くしておきます。

基数 \(b\) と法 \(p\) を適当な方法で決めておきます。 文字列 \( s = (s_0, s_1, \dots, s_{n-1})\) に対して数列 \( s' = (s'_i)_{i=0}^n\) を \(s'_i = \sum_{j=0}^{i-1} (s_j\cdot b^{i-j-1})\bmod p\) で定義します。

このとき、 \[ \begin{aligned} s'_0 &\equiv 0 \\ s'_1 &\equiv s_0 \\ s'_2 &\equiv b\cdot s_0 + s_1 \\ s'_3 &\equiv b^2\cdot s_0 + b\cdot s_1 + s_2 \\ s'_4 &\equiv b^3\cdot s_0 + b^2\cdot s_1 + b\cdot s_2 + s_3 \end{aligned} \] のようになります。重み?つき累積和みたいなイメージです。 \(s'_{i+1} = (b\cdot s'_i + s_i)\bmod p\) のようにして求められるので、\(s\) から \(s'\) は \(O(n)\) 時間で構築できます。 このとき、文字列 \(s\) のハッシュ値を \(s'_n\) とします。

このとき、\(s\) の区間 \([l, r)\) の部分文字列 \(s_{l, r} = (s_l, s_{l+1}, \dots, s_{r-1})\) のハッシュ値は \( (s'_r-s'_l\cdot b^{r-l})\bmod p\) で求められます。 \(b^i\) (\(0\le i\le n\)) を \(O(n)\) 時間で前計算しておくことで、この計算は \(O(1)\) 時間でできます。

これにより、部分文字列のペア \(s_{l, r}\) と \(s_{l', r'}\) が等しそうかどうかを \(O(1)\) 時間で判定できます。 すなわち、\(s_{l, r}\) のハッシュ値と \(s_{l', r'}\) のハッシュ値が異なれば必ず \(s_{l, r}\ne s_{l', r'}\) だし、等しければそれなりの確率で \(s_{l, r} = s_{l', r'}\) です。 確率の議論に関しては他の記事に任せます。ここ が詳しそう*1

必要に応じて複数の基数・法のペアを用意して計算することで、正しく判定できる確率は大きくできます。以下では、\(O(1)\) 時間で確率 \(1\) で正しく判定できるものとします*2

接尾辞配列

接尾辞配列 (suffix array; SA) は、文字列 \(s = (s_0, s_1, \dots, s_{n-1})\) に対して、接尾辞 \( (s_{0, n}, s_{1, n}, \dots, s_{n-1, n}, s_{n, n})\) を辞書順に並べた配列です。 ただし、\(s_{n, n}\)*3 は空文字列です。 また、実際には、文字列を陽に持つのではなく、開始位置の添字の配列として持つことが多いです。

たとえば、abracadabra に対する SA は、[11, 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2] となります。 各添字に対応する接尾辞は次の通りです。

11 (empty)
10 a
 7 abra
 0 abracadabra
 3 acadabra
 5 adabra
 8 bra
 1 bracadabra
 4 cadabra
 6 dabra
 9 ra
 2 racadabra

接尾辞配列をお手軽に知りたいときは このサイト が便利です。

つくるよ

接尾辞配列の応用に関しては他の記事とかに任せるとして、ここでは構築だけを考えます。

接尾辞配列を愚直に求めることを考えます。Rust での実装例です。

fn main() {
    let s = "abracadabra";
    let mut sa: Vec<_> = (0..=s.len()).collect();
    sa.sort_unstable_by_key(|&i| &s[i..]);
    println!("{:?}", sa);  // [11, 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2]
}

C++ の例も載せておきます。

#include <iostream>
#include <algorithm>
#include <numeric>
#include <string>

int main() {
  std::string s = "abracadabra";
  std::vector<size_t> sa(s.length() + 1);
  std::iota(sa.begin(), sa.end(), 0);
  std::sort(sa.begin(), sa.end(), [&](auto i, auto j) {
    return s.substr(i) < s.substr(j);
  });

  // 11 10 7 0 3 5 8 1 4 6 9 2
  for (size_t i = 0; i < sa.size(); ++i)
    std::cout << sa[i] << (i+1 < sa.size()? ' ': '\n');
}

最悪計算量について考えます。ソートの比較回数は \(\Theta(n\log(n))\) 回であり、比較に最悪 \(\Theta(n)\) 時間かかってしまうので、全体で \(O(n^2\log(n))\) 時間です*4。 すべての文字が a の場合とかが最悪なはずです。

さて、ここの大小比較をロリハでやることで高速化しましょうというのが今回のお話です。 ロリハの演算は \(O(1)\) 時間での ==/!= 判定ですが、これを \(O(\log(n))\) 時間での <=> 判定にします。 要するに、\(\log(n)\) 倍悪くして大小比較までできるようにしましょうということです。

\(s\lt t\) のとき、ある \(i\) が存在して \(s_j = t_j\) (\(0\le j\lt i\)) かつ \(s_i\lt t_i\) です。 なので、\(s_j = t_j\) (\(0\le j\lt i\)) なる \(i\) をにぶたんで求め、\(s_i \lt t_i\) かどうかを判定すればよいです。

\(s_j = t_j\) (\(0\le j\lt i\)) は \(s_{0, i} = t_{0, i}\) に他ならないので、これはロリハで \(O(1)\) 時間でできます。 にぶたんにより \(O(\log(n))\) 時間です。

よって、ソートの比較回数と併せて合計で \(O(n\log(n)^2)\) 時間です。

先行研究

ここに簡潔に書いてあります。いかがでしたか?

topcoder-g-hatena-ne-jp.jag-icpc.org

実装

judge.yosupo.jp

比較パートを二分探索でやると TLE したので指数探索をしました。指数探索パートの底はガチャをしました。 もちろんロリハの基数・法もガチャです。

大人気 SA-IS

rsk0315.hatenablog.com

アルファベットサイズを定数とするなり \([0, n]\) の範囲の数値で与えられるものとするなりして、\(O(n)\) 時間で構築できます。

judge.yosupo.jp

おわり

おわりです。

*1:ハッシュ値の計算方法が上記のものと若干異なりますが、大した影響はないはずです。逆向きの文字列を考えればよいので。

*2:できるものとします。

*3:これは要素に含めない場合もあるかも。

*4:毎回 \(\Theta(n)\) かかるわけではないので \(\Theta\) で言える自信がありませんでした。

全方位木 DP を指して rerooting と呼ぶ風潮に対するお気持ち表明

rerooting DP、rerooting をする DP、DP with rerooting とかなら別によさそう。

全方位木 DP 自体を指して「rerooting」と言われると気になります。 rerooting は木の根を変える操作(全方位木の中で考えられる)を指していて、全方位木 DP 自体のことを指しているわけではないと思っています。

例を出すよ

DP 以外の文脈で rerooting という言葉が使われているのを挙げてみます。 Euler tour を管理するデータ構造で、根とする頂点を変える操作が rerooting と呼ばれています。

http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/17/Slides17.pdf

上の資料では、森に関するクエリ処理をするデータ構造を考えています。 対象のクエリは「この辺を追加してね」「この辺を削除してね」で、ループはできないことが保証されています。

森を Euler tour の集合として表現すると、辺の追加や削除に際して、Euler tour の根の頂点を変える操作ができると楽になるようです。 そこで、その操作名が rerooting と呼ばれています。

例おわり。

DP の名前ではなくて、単に、より一般的な操作の名前として捉える方が自然な単語に思えます。

そういえば

splay tree ではアクセスしたノードを根に持っていく操作を splay と呼んでいましたね*1

そこで思ったんですが、splay tree で splay をする際に DP の更新をするようにすれば、順に頂点をなめることで全方位木 DP で得たいものを得られたりしませんかね? splay は amortized \(O(\log(n))\) time ですが、順になめたときは amortized \(O(\log(\log(n)))\) time という結果もあった気がします(詳細見失いました、嘘かも)。

何にせよ普通に BFS/DFS した方が速そうですが...

おわり

もしかしたらえびちゃんの勘違いで、全方位木 DP 自体を指して rerooting と呼んでいる人はいないかもしれません?

お気持ち表明シリーズが好きな人におすすめ(今回の記事より内容ずっしりめです): rsk0315.hatenablog.com

*1:link/cut tree では evert という呼ばれ方もあったような...?

インタラクティブ問題のデバッグに関してなど

インタラクティブ問題は手元でのデバッグが面倒がちなので、いやだと思っている人が多そうです。 coproc というシェルの機能を使えばそこそこ簡単にできないかな?と思ったので、書いてみます。

まえおき

簡単とは言っても、以下のものは自分で書く or 生成する必要があります*1

ジャッジについては、次のような仕様を満たしていてほしいです。

  • 入力データのファイル名をコマンド引数で受け取る
    • あるいは、ジャッジがランダムで生成してもよいです、ここはよしなに。
    • 標準入力はクエリとのやりとり用にしたいので使えません。
  • クエリを標準入力から受け取る
  • 返答を標準出力に書き出す
  • デバッグ用の出力を標準エラー出力に出してもよい
  • AC ならステータス 0 で終了、そうでなければ 1 などで終了*2
    • 要するに、return ac? 0: 1; みたいなことをしてほしい。

やります

さて、解答のプログラム ./sol とジャッジのプログラム ./judge と入力ファイル infile を用意できたとします。 このとき、次のようにできます。シェルによって違うので、各々説明します。

Bash

実行例:

bash-5.1$ coproc ./sol
[1] 27352
bash-5.1$ ./judge infile <&${COPROC[0]} >&${COPROC[1]}
AC: ok
[1]+  Done                    coproc COPROC ./sol

実行例なので出力も混ざっていますが、実際に書く必要があるのは次の部分だけです。

coproc ./sol
./judge infile <&${COPROC[0]} >&${COPROC[1]}

coproc をつけてコマンドを実行すると、標準入出力以外と入出力をやりとりするものとして開始されます(パイプと呼ばれる機構とやりとりします)。 入力先のパイプは file descriptor*3 の形で教えられ、その値は ${COPROC[1]} に入っています。出力先も同様で、${COPROC[0]} です。

file descriptor が fd のものにリダイレクトしたいときは、<&fd>&fd の形を使えばよいです。 標準エラー出力を標準出力にまとめるときに 2>&1 というのを見たことがある人もいると思いますが、標準出力の file descriptor が 1 なので、こういう感じの書き方になっているわけですね。 標準入力は 0標準エラー出力2 です。

coproc をつけて実行したコマンドにとっての入力先は ${COPROC[1]} に入っていますが、それに対して書き込む(入力を与える)コマンドにとっては ${COPROC[1]} は出力先なので、標準出力の番号に対応する 1 に値が入っていると考えるとよさそうです。若干ややこしいですね。

AC: ok標準エラー出力に対する書き込みです。実際には、次のような内容があると便利かもしれません。

  • どういうクエリを受け取ったか
  • どういう返答をしたか
  • QLE や WA であればその詳細

Zsh

実行例:

% coproc ./sol
[1] 27741

% ./judge infile <&p >&p
[1]  + done       ./sol
AC: ok

書く必要がある部分:

coproc ./sol
./judge infile <&p >&p

こっちの方が短いですね。Zsh では、coproc で作ったコマンドに対してリダイレクトしたいときは <&p>&p が使えるとのことなので、それを使えばよいです。 他は Bash と同様です。

そのほか

IDE とかを使っていてシェルと仲よくない人もいるらしいです? よしなにがんばってほしいです...

あと fish-shell の人もよしなにがんばってほしいです。

そうなんだけど

github.com

oj っていうツールがあるんですが、次のようなことができます。

% oj t/r -c ./sol './judge infile'

おまけ

macOS にデフォルトで入っている Bash のバージョンは化石であることで有名です。

bash-3.2$ coproc
bash: coproc: command not found

brew install bash とかをするとよいです。

おわり

結局、ジャッジを書くのが面倒という問題からは逃れられないので困ります(これは構築などのスペシャルジャッジが必要な問題についてもそう)。 ジャッジを書くパートさえできたら、解答とジャッジのやりとりパートはわりと簡単じゃんというお話でした。

ジャッジを書くパートは面倒で、特に adaptive/adversarial な問題では、厳しく書くのは大変です。 これは、クエリのやりとりに矛盾しない入力データであれば、ジャッジ側が "後出し" できるといった問題設定のことです。

それはそれとして、interactive や reactive などの表記揺れ(表記というか表現というか)があって、どれを使うべきなんだろう〜と思っています。

*1:やっぱり面倒じゃん、解散。←?

*2:ステータスを -1 などの負数にする人がよくいますが、これは予約された値であり、よくなかった気がします。文献は見失いました。

*3:ここでは、単にファイルやパイプを特定するための表し方の一つ、くらいに認識しておけばいい気がします。

誤差許容ジャッジちゃんと遊んでみる (part 0)

part 1 以降があるかはわかりません。

導入?

競プロで、「絶対誤差または相対誤差が \(10^{-6}\) 以下ならば正解と判定される」といった文言はちょくちょく見かけます。

思い出すシリーズ \(2e-3\) atcoder.jp

その昔、これに対して NaN と出力するだけで AC になるなどの脆弱性もありました。

atcoder.jp

最近の問題のジャッジではそうしたことは起こらないはずです。

atcoder.jp

自前で書くとそういう脆弱性を入れがちなので、testlib とかのライブラリなどを適切に使うとよいと思います。 普段 contestant として「お行儀のよい」入力に慣れがちな競プロ er は、そうした脆弱性に疎いんじゃないかな?という気がしています(偏見)。

rian.hatenablog.jp

本題?

contestant 的には、たとえば答えが 1.5 のときに 1.50 とか 1.50000000000000000 とか 1.4999999999999999 とかを出力しても WA になってほしくないですよね。 あるいは、指数表記を許すと言われているジャッジであれば、15e-1 とか 150000000000000000000e-20 とか 0.000000000149999999999999e+10 とかを出力しても許されたいわけです。

ということで、ジャッジちゃんと遊びました。

1.5000...00 の形式 atcoder.jp

15000...00e-xx の形式 atcoder.jp

0.000...0015e+xx の形式 atcoder.jp

どれも AC になってくれて、えらいなと思いました。\(2^{27}\) 文字出力しています*1。これを超えると OLE です。

話題 1

環境によっては、指数部が大きすぎると、無限精度で行った場合と異なる結果が返ってきそうです。 実数を入力として受け取り、double としてパースし、それを出力するプログラムを考えます。

#include <cstdio>
int main() {
  double x;
  scanf("%lf", &x);
  printf("%f\n", x);
}

これに対して、2000...00e-xx の形式で、2.0 と等しいはずの値を与えてみます。

% echo 20.0e-1 | ./a.out
2.000000

% (e=19999; printf 2; repeat $e printf 0; echo e-$e) | ./a.out
2.000000

% (e=20000; printf 2; repeat $e printf 0; echo e-$e) | ./a.out
20.000000

% (e=20306; printf 2; repeat $e printf 0; echo e-$e) | ./a.out
19999999999999999720621195205129155434005283676252727750499321471767131705345487698129692828457921333572758560785309230786706345700504206672551904741230794021461383329378750357138079702146292679283246532142253440022040339106608037192915625377123894402342976922345843644278133859702564244005353335500042141696.000000

% (e=20307; printf 2; repeat $e printf 0; echo e-$e) | ./a.out
inf

わーびっくり。AtCoder のコードテストの環境では再現しませんでした。 処理系によるのかな?

Because computers are finite, C++ implementations are inevitably limited in the size of the programs they can successfully process.

と規格にも書かれているし、そういうのも許されているのかもしれません? 上記は入力側じゃなくてプログラム側の話な気もするので、やっぱり許されてないかもしれません?

ソースコード中にそうしたリテラルを書いた場合はちゃんと出力してくれました。

% cat <<EOF | g++-10 -xc++ - -O9 -o fl && ./fl
cmdand heredoc> #include <cstdio>
cmdand heredoc> int main() {
cmdand heredoc>   double x = $(e=100000; printf 2; repeat $e printf 0; echo e-$e);
cmdand heredoc>   printf("%f\\n", x);
cmdand heredoc> }
cmdand heredoc> EOF
2.000000

cmdand heredoc> もプロンプトですが、syntax highlighting がこわれてしまった)

話題 2

ちなみに、浮動小数点数には 16 進のリテラルもあって、0xH.HHHp+D の形式です。H の部分を 16 進数で書き、D にはビットシフトの幅を書きます。 たとえば、\(2.75 = (2^3+2^1+2^0)/2^{-2}\) なので、2.75 の代わりに 0xbp-30.x1.6p+1 などと書けます。

printf("%a\n", x) などとすればこの形式で出力できますが、ジャッジはこの形式には対応していないようでした(かなしいね*2)。

atcoder.jp

おわり

今回は ABC 130 C のジャッジちゃんと遊びましたが、別のジャッジちゃんは別の挙動をするかもしれません。 誤差まわりについても遊んでみたいかもしれませんね。

*1:出力内容によっては 1 文字少ないかもです。

*2:別にかなしくはなくない?

bitset 高速化が定数倍高速化という風潮に対するお気持ち表明

「bitset で 64 倍高速化できます」「64 は定数なのでオーダーは変わりません」のような説明は、競プロ界隈でたびたび見かけます。

AGC の解説 とかも。

「定数倍高速化を軽視する風潮に対するお気持ち表明」や「競プロのような入力に上限がある場合でもオーダーを信仰する風潮に対するお気持ち表明」などは、一旦おいておきます。

今回のメインは、「長さ \(n\) の bit 列の bitwise AND/OR や shift にかかる時間は \(\Theta(n)\) か?」(あるいは、そう仮定するのは妥当か?)という話です。

補足

オーダー記法に慣れていない人が以下で怯えないように、さくっとまとめておきます。

  • \(\Theta(f(n))\):ちょうど \(f(n)\) のオーダー。
    • 競プロ界隈で言うところの \(O(f(n))\) に近そう。
  • \(O(f(n))\):高々 \(f(n)\) のオーダー。
    • \(O(n^3)\) と書いたとき、実際には \(\Theta(n^2)\) かもしれない。
  • \(\Omega(f(n))\):少なくとも \(f(n)\) のオーダー。
  • \(o(f(n))\):\(f(n)\) より真に小さいオーダー。
  • \(\omega(f(n))\):\(f(n)\) より真に大きいオーダー。

小文字の方は今回は使いません。

導入

次のような問題を考えてみます。

\(0\) または \(1\) からなる長さ \(n\) の列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられます。これが回文か判定してください。

  1. for \(i \in \{0, 1, \dots, n-1\}\) do
    1. if \(a_i \ne a_{n-i-1}\) then
      1. return no
  2. return yes

愚直には、このようなアルゴリズムが考えられるわけですが、これの計算量はどうなるでしょう? 何の仮定も無しに \(O(n)\) 時間(+ worst \(\Theta(n)\) 時間)だと言い切っていいでしょうか? \(i\) のインクリメントや \(n-i-1\) の計算、\(a\) へのアクセスが \(O(1)\) 時間でできるものと仮定しているはずです(もっと言えば、1 bit の等価判定を \(O(1)\) 時間と仮定しているはずです。さすがにこれくらいは仮定したいですが)。

読者の中には、「\(a\) を順方向と逆方向にシーケンシャルアクセスするだけでいいからそれらの仮定はいらないだろう」と言う人もおられるかもしれない*1ので、別の例も出します。

\(0\) 以上 \(2^n\) 未満からなる長さ \(n\) の整数列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられます。その後、「与えられた \(i\) と \(j\) に対して \(a_i+a_j\) の値はなんですか?」という形式の \(m\) 個の質問に答えてください。

これは \(O(n+m)\) 時間と言えてほしいですが、何の仮定も無しには言えません。 そもそも各整数をどういう形式で表すのかについても触れていません。 「ひとつの整数を表すのに \(2^n -1\) 個の連続する bit を用い、そのうち(連続するとは限らない)\(x\) 個の bit が \(1\) で残りが \(0\) のとき、\(x\) を表すとする」などと言われては大変扱いにくいので、もう少しマシなものを要求したいです。 コンピュータで扱いにくいものの話をしてもしょうがないので、2 進法で表すのがいいかなとなります*2

また、整数 \(i\) を用いて \(a_i\) に \(O(1)\) 時間でアクセスできることが要求されます。 \(a\) の長さは \(n\) であることから、\(\log(n)\) bits 程度の整数は \(O(1)\) 時間で扱えないとお話にならないことがわかります。 \(a_i+a_j\) の計算もしなきゃなので、\(\log(n)\) bits 程度の加算も \(O(1)\) 時間でしたいです。

word RAM の話

こうした要望に合った計算モデルとして、word RAM というのがあります。次のような仮定です。

  • \(U=2^u\) 個の word からなる配列をメモリと呼ぶ。
    • 入力はこのメモリに収まる必要がある。
  • word をポインタとして扱える。
    • word を添字として用いてメモリ(の全範囲)にアクセスできるということ。
  • 長さが \(O(1)\) の連続する word に対する読み書き、四則演算 (+, -, *, /, %)、ビット演算 (&, |, ^, !, <<, >>), 比較演算 (==, <, etc.) は \(O(1)\) 時間でできる。
    • ! はビット反転。C とかで言うところの ~

word によってメモリにアクセスできることから、word は最低でも \(u\) bit 必要です。 word の bit 長を \(w\) とすると \(w\ge u\) です。

これらから、連続する \(u\) bit に対する各種演算が \(O(1)\) 時間でできることが従います。 ただし、「メモリから飛び飛びの \(u\) 個の bit を集めてきて、結合してひとつの整数と見なし、それらを用いた演算を行う」ということは \(O(1)\) 時間でできるとは言っていないことに注意してください。

本題

さて、元々の話に戻ります。

長さ \(n\) の bit 列に対するビット演算の計算量は?

連続する \(n\) 個の bit 列、すなわち \(n/w\) word に対する演算となります。 \(w\) は最低でも \(\log(n/w)\) bit 必要なことから \(w \ge \log(n/w)\)、すなわち \(w\cdot 2^w \ge n\) となります。

式変形がんばるよ \(w\cdot 2^w = n\) の形の式を解くのは初等的にはつらいです。Lambert の \(W\) 関数 というのがあります。 一般には複素数で定義されますが、ここでは実数についてのみ考えます。 \[ ye^y = x \implies y = \begin{cases} W_0(x), & \text{if }x \ge 0; \\ W_{-1}(x), & \text{if } -1/e\le x\lt 0. \end{cases} \] ここでは \(x\ge 0\) のみ気にするので、\(W_0\) のみ考えます。 \[ \begin{aligned} w\cdot 2^w &\ge n \\ w\cdot 2^{w\cdot\log_2(e)\cdot\log_e(2)} &\ge n \\ w\cdot e^{w\cdot\log_e(2)} &\ge n \\ w\cdot\log_e(2)\cdot e^{w\cdot\log_e(2)} &\ge n\log_e(2) \\ w\cdot\log_e(2) &\ge W_0(n\log_e(2)) \\ w &\ge W_0(n\log_e(2))\cdot\log_2(e). \end{aligned} \]

また、\(W\) 関数について、以下のことが知られています*3。 \[ x\ge e \implies \ln(x)-\ln(\ln(x)) \le W_0(x). \] これらから、\(w\in \Omega(\log(n/\log(n)))\) が言えそうです。 がんばりおわり。

不等式を示すだけなら、\(W\) を使わなくてもできるかもです。

結局、\(w\in \Omega(\log(n/\log(n)))\) が言えたので、\(n/w \in O(n/\log(n/\log(n)))\) となります。 すなわち、bitset 高速化は(word RAM の文脈では)\(O(\log(n/\log(n)))\) 倍の改善と言えそうです*4

あるいは、入力が bit 列以外にもあるなどでメモリが \(\Omega(n)\) word 必要なら、\(w\in\Omega(\log(n))\) とできるので、\(O(\log(n))\) 倍の改善と言えそうです。

(追記:2021/06/11)\(O(n^2/w) = O(n^2/\log(n))\) になるやつとかを考えていました。メモリを \(\Theta(n)\) 使って \(O(n/w)\) だと、\(O(n)+O(n/w)=O(n)\) で得できなさそう?

おまけ

別のモデルの話

たとえば、もっとやばい計算モデルを仮定して、「任意のサイズの整数の四則演算は \(O(1)\) でできます」というのがある程度の妥当性をもって言えれば、bitset 高速化は \(n\) をひとつぶん落としたと主張できそうです。

word RAM の元々の論文*5では、

これこれの論文では長さ \(n\) の整数配列 \(a\) のソートを \(O(n)\) 時間で達成したと述べているが、\(n^2 \log(\max a)\) の長さ(ビット?)の除算を \(O(1)\) 時間でできると仮定した上でのアルゴリズムであり、やばいだろ

といった旨のことが書かれていました。

(追記)上の式では \(w\) の下限にしか触れていないので、別に \(w=n\) のようにワードサイズがやばいモデルを仮定することもできそうです。が、ちょっと乱暴だと思います。また、メモリを無駄に使うことで「\(w\) がもっと必要でしょう」と主張することもできそうですが、無駄に使ったメモリのぶんの時間のせいで損をしそうです。

www.cs.cmu.edu

今回の内容に関連する講義資料です。word RAM 以外にも、Turing machine論理回路を用いた場合に計算量はどうなるか?といったことが書かれています。

許容する演算の話

word RAM においては word size の四則演算を \(O(1)\) と言っていますが、乗算や除算はこれに含めないとする立場もあるようです。 これは、特定の条件を満たす回路によって加算は実現できるが乗算は実現できないという事情によるようです。 \(n\) bit の乗算が \(M(n)\) 時間でできれば、Newton 法によって \(n\) bit の除算も \(O(M(n))\) 時間でできるので、乗算を仮定するなら除算も仮定されそうです。

また、立っている最上位 bit の位置は、乗算を許せば次の手法で \(O(1)\) 時間で得られます。

rsk0315.hatenablog.com

これにより、立っている最下位 bit が n & -n で得られることと合わせて、立っている最下位 bit の位置も \(O(1)\) 時間で得られます。

word RAM 上のアルゴリズムの話

こういう記事があります。

qiita.com

まとめ

\(O(n/w)\) などの \(w\) は定数ではなくて、入力サイズ \(n\) に依っていると見なす立場もあるよ、という話でした。

マシンが入力に依ることに納得がいかない人は、「大きいサイズの問題を、メモリの少ない昔の PC で解くのは不可能」みたいなことを考えてみるといいかもしれません? 大きなメモリをちゃんと扱うことができるマシンであれば、それに伴っていくらか大きい値も扱えるようになる、といったような気持ちに近い気がします。

おわり

log は定数学派の人にとっては bitset 高速化は定数倍高速化ということがわかりました。いかがでしたか?

*1:「インクリメントはならし定数時間なので〜」とか思った人もいるかも?

*2:当然、文脈によってはコンピュータに縛られる必要はありませんが、ここでは一応競プロに近い文脈なので。

*3:Hoorfar, A., & Hassani, M. (2008). Inequalities on the Lambert W function and hyperpower function. J. Inequal. Pure and Appl. Math, 9(2), 5-9.

*4:このあたり、記法が怪しいので困りました。

*5:Fredman, Michael L., and Dan E. Willard. "Surpassing the information theoretic bound with fusion trees." Journal of computer and system sciences 47.3 (1993): 424-436.

素数判定するよ

\(n\) 以下の素数の個数を求める関数 \(\pi(n)\) を持っていたとします。 このとき、\(n\) の素数判定は \(\pi(n)-\pi(n-1) = 1\) かどうかでできます。

fn is_prime(n: usize) -> bool {
    n > 0 && prime_pi(n) - prime_pi(n - 1) == 1
}

たとえば \(O(n^{3/4}/\log(n))\) でできます*1

お粗末さまでした。

おまけ

素数の数え上げが気になる人向けの記事:

rsk0315.hatenablog.com

*1:素直に \(O(n^{1/2})\) 時間の試し割り法をしましょう。