よく出るあの級数！情報系なら絶対覚えるべき計算量の話！

皆さん、久しぶり！競プロを始めてから実装の話ばかりしていた。いよいよアルゴリズムの原点に戻った！今回は例の $\displaystyle \sum_{i=1}^N \log{N}$ を見に行きたいと思う。

この級数はどこで出るの？

まずは結論から言うと、この級数は $\Theta (N \log{N} )$ クラスに属す。これでちょっと見覚えがあるのか？セットを使って配列から重複を取るアルゴリズムは配列の要素を順に見て行き、そしてセットにいるかどうかをチェックする。配列の長さをNとして、セットのサイズをKとする。クエリごと $O(log{K})$ の時間がかかる。その結果、全体の計算量はこの級数になる。

その他にもLIS問題、最短経路問題など超有名問題で出てくる大人気級数である。

いきなり現れる $\Theta$ は一体なんだ？

授業ではビッグOを教えることが多いですが、ビッグOはあくまで最悪の場合を指す。実際 $N$ も $N \log{N}$ も $O(N \log{N} )$ なので、ビッグOは厳密ではない。その代わりに、 $\Theta(N \log{N})$ はちょうどこのクラスにいる関数の集合。

前の例を持ち上げると、セットを使ったあのアルゴリズムは最悪 $O(N log{N} )$ だけじゃなくて、これ以上早くなることもない。

数学コーナーはみんな大嫌いだけど見ないと背が伸びない

まずここで証明したい命題を貼りましょう！

$☆証明していくぞ☆：\log{N!} = \Theta \left(N \log{N} \right) \\$

この問題は二つの問題に分けて考えましょう！まずは

$\log{N!} =O \left(N \log{N} \right) \\$

これは自明的だ。 $N \log{N} = \log{N^N}$ から、 $\log{N!} \leq \log{N^N}$ は明らかなことだ。では難しい方へ進むぞ！

$N \log{N} =O \left( \log{N\!}\right) \\$

今回は帰納法でやる。まずはある $X$ に対して、 $X \log{X} \leq k\log{X!}$ が成立とする。これを仮説1と呼ぶ。そして $N=X+1$ の時の式を見てください。

$\displaystyle \left(X+1\right) \log{\left( X+1 \right) } = X \log{ X } + X \log{ \frac{X+1}{X}} + \log{\left( X+1 \right)} \quad (1.1)\\ \log{\left( X+1 \right) ! } = \log{X!} + \log{\left( X+1 \right)} \quad (1.2) \\$

今からはただ $k$ を式(1.2)にかけたものは依然式(1.1)より大きいことを示せば万事解決。今の式を見れば、ほどんど見たことある顔で安心した。でも待って、式(1.1)の $X \log{ \frac{X+1}{X}}$ はどんどん大きくなるじゃないかっと思うと、実際は上限がある！

$補助定理：X \log{ \frac{X+1}{X}} \leq 1　\\$

調和級数の時使った技を思い出してね！ $\log{ \frac{X+1}{X}}$ は $\displaystyle \int_{X}^{X+1} \frac{1}{t} dt$ と等しい。この積分の区間での最大値は $t$ イコール $X$ の時から、 $\log{ \frac{X+1}{X}} \leq \frac{1}{X}$ がわかる。さらに式(1.1)は式(1.3)より小さいことが分かった。

$X \log{ X } + 1 + \log{\left( X+1 \right)} \quad (1.3)\\$

定数 $k$ を式(1.2)に掛けると $k \log{X!} + k \log{\left( X+1 \right)}$ が得られる。仮説1を使えば $k\log{X!}$ と $X \log{ X }$ を式1.2と式1.3から消せる。残る部分は $1 + \log{\left( X+1 \right)}$ と $k \log{\left( X+1 \right)}$ だけ。定数 $k$ を予め大きくしたら $k \log{\left( X+1 \right)} \gt 1 + \log{\left( X+1 \right)}$ も成立する。当然のことことなんですが、 $N=2$ の時 $k\log 2 \gt \log 4$ が成立するので証明終了。Q.E.D