基本的な計算量まとめ - ロアちゃんかわいい

おはようございます。

いつぞやの記事で大ざっぱな意味を書いた覚えがあるんですが、計算量の評価についてのあれこれをメモしておこうと思います。

知っているとTLEなどを防ぎやすくなるだけでなく、解法を思いつきやすいという利点があるので計算量評価に慣れることは有効だと思います。

・計算量とは
コンピューターに何らかの処理をさせるとき、その処理にかかる時間は処理内容によります。
元を辿ればコンピューターは電子回路で設計されているので、同じような内容でも各計算事に若干の誤差は考えられますが、使用者である僕たちが認識することの出来ない程度の誤差なので無視しても問題ありません。

・ランダウの記号
よく見るO()の記号。競技プログラミングではもっぱら計算量の評価に使われますが、本来は数学で関数の挙動を考える時、漸近的な評価に対して用いる記法です。
プログラミングで計算量を評価するために使う定義は次のようにすればよいかと思います。
「十分大きな全ての実数xに対して定義されている実数値関数f(x)、g(x)に対し、
$f(x)$ が $O(g(x))$ である」
を
「実数 $x_0, M$ が存在し、 $x > x_0 ⇒ f(x) < Mg(x)$ となる」
と定義する。
これだと大雑把すぎる評価を招きかねないですが、より厳密な評価が得られる場合はそれより緩い評価は使わないとしておけば十分でしょう。
厳密な解析が難しいものもあるので、この方がよいと思います。

・ランダウ記号の性質
$f_1(x) = O(g_1(x)), f_2(x) = O(g_2(x)) ⇒ f_1(x)f_2(x) = O(g_1(x)g_2(x)), f_1(x) + f_2(x) = O(g_1(x)) + O(g_2(x))$ （積と和の評価）
$O(O(f)) = O(f)$ （合成しても同じ）
$O(f + g) = O(f) + O(g)$ （線形っぽいやつ）
$O(f) + O(g) = O(max{O(f), O(g)})$ （ランダウ記号の和）
$O(f)O(g) = O(fg)$ （ランダウ記号の積）
$O(kf) = O(f)$ （定数kは無視できます）
$O(c) = O(1)$ （定数倍は1と表記します）

……正直もっと厳密なのが書けそうですが、実用的には使い方を覚える方が大事なので余り気にしないことにします。（これを見た人がもっといいのを知っていたら是非教えてください）

・ $O(1)$
定数倍ですね。宣言、代入などがこれに当たります。

・ $O(N)$
定数倍の処理をN回繰り返す場合が該当します。上の面倒な性質を使うと、
（定数）×N = O(1 × N) = O(N)
みたいな感じで評価できます。

・ $O(N^2)$
バブルソートなどが該当します。定数倍の処理の回数が1+2+3+…+N = N(N+1)/2 なので、最大次数の項以外の項や定数倍を無視することで評価が得られます。

・ $O(logN)$
二分探索などが該当します。要素数を2で割っていくので、その回数をxとすると
大体 $2^x = N$ とするとx = logNとなります。
対数なのでとても高速です。

利用例として、昨日のD問題（https://atcoder.jp/contests/abc134/tasks/abc134_d）の計算量の評価として
O(N+N/2+N/3+…+N/N) = O(N(1+1/2+1/3+...+1/N))
と考えて、
$\sum_{k=1}^{N} \frac{1}{k}$ を図を描いて、積分を使って上から評価してやるとO(logN)になるので、結局
O(NlogN)と見積もることが出来たりします。

以上の組み合わせで、基本的な計算量は評価できます。さらばTLE。

ではおやすみなさい。