【第7回】計算量

その解法、 TLE しない？

以下の問題の解法を考えてみましょう。

整数 $N$ が与えられるので、 $1$ から $N$ までの総和を求めてください。

多くの人は主に以下の 2 つの解法が思い浮かぶかと思います。

for 文を使って $1$ から $N$ まで足していく
等差数列の和の公式を使って、 $\dfrac{N (N + 1)}{2}$ を計算する

これらの計算回数を考えてみましょう。 1 番の解法では、 $N$ 回の足し算を行います。これに対して、2 番の解法では、足し算・掛け算・割り算の 3 回の計算で済みます。

このように大まかな計算回数を見積もる指標の 1 つに、 計算量 というものがあります。計算量を見積もることで、コードを提出する前に TLE を回避することができます。 AtCoder では TLE とジャッジされるとペナルティが課せられるため、処理対象のデータが非常に大きくなった時の処理時間を大雑把に評価することが大切です！ (1 ナノ秒かかる処理を 10 兆回ループさせると $1 \text{ ns } \times 10^{13} = 10^4 \text{ s}$ 、つまり 3 時間もかかってしまいます......)

計算量の記法と性質

オーダー記法

先程の問題の解法 1 と解法 2 の計算量を見積もってみましょう。

解法 1 は for ループを使うため、 $N$ に比例した計算回数 がかかります。これを計算量を表す記号を用いて $\Omicron(N)$ と表記します。

これに対して、解法 2 は $N$ の値は計算時間に影響を及ぼしません。つまり、計算回数は一定です。これを $\Omicron(1)$ と表記します。

計算量の表記には、このような オーダー記法 を使います。代表的なオーダーを処理時間が短い順 (性能が良い順) に並べると、以下のようになります。

$\Omicron$ 記法	名前	使用例
$\Omicron(1)$	定数時間	`vector` でのランダムアクセス、 `queue.push`
$\Omicron(\log N)$	対数時間	ソート済み配列の二分探索
$\Omicron(N)$	線形時間	ソートされていない `vector` での値の探索
$\Omicron(N \log N)$	準線形・線形対数時間	`sort`、 `stable_sort`
$\Omicron(N^2)$	二乗時間	二重ループ
$\Omicron(N^a)$	多項式時間 ( $a \geq 1$ )	行列計算 ( $N^3$ )
$\Omicron(a^N)$	指数時間 ( $a \geq 1$ )	愚直な素数探索と因数分解 (良い方法ではない)
$\Omicron(N!)$	階乗時間	順列全探索、 TSP (巡回セールスマン問題)

下に行けば行くほど計算量が大きく、処理時間がかかります。

より厳密には...

プログラムは必要な計算をするために、メモリを使います。入力に対してどのくらい計算時間やメモリの使用量が変化するかを示す指標が計算量です。

時間計算量: 必要な計算 (四則演算や数値の比較) の回数
空間計算量: プログラムが実行される際に必要なメモリの量

単に「計算量」といった場合、競技プログラミングでは時間計算量を指すことが多いです。しかし、厳密な計算回数やメモリ使用量(KB とか)を求めることは難しいです(実装方法やプログラミング言語によって異なるため)。そのため計算量を見積もるときには、大雑把に評価できる オーダー記法 がよく使われます。

$\Omicron$ , $\Omega$ , $\Theta$ の記法がありますが、競技プログラミングでは $\Omicron$ 記法がよく使われます ( この場合だと、厳密には $\Theta$ の意味で使われることが多いようです ) 。

$\Omicron$ はアルファベットの $O$ ではなくて、ギリシャ文字の「オミクロン」です。アルファベットで代替されることも多いようです。

$n$ が十分大きいとき、それぞれの記号は以下のように使われます。

表記	読み方	意味
$f(n) = \Omicron(g(n))$	$f(n)$ のオーダーが $g(n)$ より小さい	$f(n)$ は $g(n)$ と同じくらいかまたは遅いスピードで増加する
$f(n) = \Omega(g(n))$	$f(n)$ のオーダーが $g(n)$ より大きい	$f(n)$ は $g(n)$ と同じくらいかまたは速いスピードで増加する
$f(n) = \Theta(g(n))$	$f(n)$ のオーダーが $g(n)$ と等しい	$f(n)$ は $g(n)$ と同じくらいの速度で増加する

厳密な定義はここでは紹介しませんが、気になる方は調べてみてください。情報工学科の「離散数学」で用いられている教科書、守屋悦朗さんの『やさしい離散数学』にも載っていると思います。

オーダー記法の性質

オーダー記法には以下の性質があります。

$f(n) = \Omicron(g(n)), g(n) = \Omicron(h(n)) \Rightarrow f(n) = \Omicron(h(n))$ (推移律)
$\Omicron(f(n)) + \Omicron(g(n)) = \Omicron(f(n) + g(n))$
$\Omicron(f(n)) \times \Omicron(g(n)) = \Omicron(f(n) \times g(n))$
$\Omicron(cf(n)) = \Omicron(f(n))$ (定数倍)
$\Omicron(\Omicron(f(n))) = \Omicron(f(n))$ (冪等性)

また、 $f(n)$ が多変数になっても同様に成り立ちます。

表記の問題点

オーダー記法の意味を考えると、例えば $\Omicron(x) = \Omicron(x^2)$ という式が成り立ちます。ですが、これは「 $x$ を十分に大きくしたときに、 $x$ (左辺) は $x^2$ (右辺) と同じくらいかまたは遅いスピードで増加する」という意味なので、 $\Omicron(x^2) \neq \Omicron(x)$ であることに注意してください。

コンピュータ関連におけるオーダー記法では、できるだけ簡単な形に式を変形して表記することが一般的です。基本的には以下のルールさえ覚えれば変形することができます。

ルール 1: 計算量が一番大きい項だけを残す

$\Omicron(N^2 + N + \log N)$ は $\Omicron(N^2)$ と表記すれば十分です。

ルール 2: 定数倍は無視する

$\Omicron(3N^2)$ は $\Omicron(N^2)$ と表記します。

また、実は $\log$ の底は何でもよいです。

$\Omicron(\log_c N)$ を考えてみると、 $\displaystyle \log_c N = \frac{1}{\log c} \times \log N$ と変形できるため、 $\log_c N$ は自然対数 $\log N$ を定数倍したものと見なすことができます。よって、 $\Omicron(\log_c N)$ は $\Omicron(\log N)$ と表記することが多いです。

計算機科学の分野では、底は 2 とみなされるケースもあります ( 二分探索や 2 進数をよく扱う影響かも？ ) 。

オーダー記法の練習

$N + 100$
$25N + N^3 + N^2$
$3 + 5$
$2^N + N^2$
$N^2 + M$
$\log_{2} N$
$\log_{10} N^{32}$

答え

$\Omicron(N)$
$\Omicron(N^3)$
$\Omicron(1)$
$\Omicron(2^N)$
$\Omicron(N^2 + M)$
$\Omicron(\log N)$
$\Omicron(\log N)$

計算量と競プロの関係

競技プログラミングでは、計算量は以下のような使い方ができます。

アルゴリズムの最悪の計算量をオーダー記法で求める。
問題文の「制約」から、最も時間のかかる入力 ( $N = 10^5$ など ) を探す。
ステップ 1 で求めた計算量に対して、ステップ 2 で見つけた入力を代入する。

ステップ 3 で求めた値によって、

$10^7$ 以下: 間違いなく間に合う
$10^8$ : 間に合うことが多い
$10^9$ : 限界ギリギリ
$10^{10}$ : ほぼ間違いなく TLE する。アルゴリズムを変える必要あり。

といった感じで、提出前に未然に TLE を回避することができます。

計算量と対数関数

計算量に $\log$ が出てくるアルゴリズムとしては、二分探索やエラトステネスの篩などが代表的です。

二分探索は、配列から特定の値を探し出すために用いられるアルゴリズムです。そして、このアルゴリズムは非常に高速で、配列の調べる範囲が 1 回の操作をするたびに半分になるという性質があります。このため、 $N$ 個の要素から特定の値を探す場合、最大でも $\log_2 N$ 回の操作で探し出すことができます。

また、エラトステネスの篩は素数を求めるアルゴリズムです。ある数 $N$ 以下の素数を全て求めることができ、計算量は $\Omicron(N \log \log N)$ となります。

アルゴリズムの詳しい説明はここでは割愛しますが、計算量が $\log N$ や $N \log N$ 程度に収まるアルゴリズムは、 $N$ が大きい場合にも高速に動作するため、競技プログラミングでは重宝されます。