計算量

N % K が 前章のプログラムで何回程度実行されるか考えてみよう. このプログラムが最悪の動作をするのは, N が素数の時である. N が素数の時には, K は N に達するまで 1 づつ増え つづける. したがって, N 回余りの計算が実行される. よって N の 2 進数であらわした桁数を $m$ とすると, $O(2^m)$ 回程度の余りの計算が実行されることになる.

ここで $O(2^m)$ は $O$-記法とよばれ, $m$ が十分大きい時, $[C 2^m + (\mbox{$C' 2^m$\ より小さい数})]$ 程度の大きさ であるような数をあらわす. ここで $C$ は定数である. 例えば, $2 m^2 - m = O(m^2)$, $100 m \log m + 5000 m = O(m \log m)$ である.

プログラムやアルゴリズムの実行時間やメモリ使用量を 入力データサイズの関数で評価することを計算量の評価という. 実行時間(時間計算量)を調べるには, 一番多く実行される文の実行回数を目安にすると よいであろう.

たとえば, 上のプログラム prime_factorization(N) の 場合は N に素数をいれた場合, ループが O(N) 回実行される. したがって次のような定理がなりたつのはほぼ明らかであろう.

定理 7.1   素因数分解アルゴリズム prime_factorization(N) の最悪時間計算量は $O(2^m)$ である. ここで N を 2 進数であらわしたときの桁数を $m$ とする.

アルゴリズムの性能表示は $O(m), O(m^2), O(\log m), O(m\log m), O(e^m)$ など $O$-記法を利用しておこなわれる. $O(\log m), O(m), O(m\log m), O(m^2)$ がどの程度違うか 表にしてみてみよう. ここで $\log m$ は $2$ を底とする $m$ の対数である.

$$\begin{array}{\vert c\vert c\vert c\vert c\vert c\vert} \hli... ...000 \\ m^2 & 100 & 10000 & 100億 & 1 兆 \\ \hline \end{array}$$

この表を見ればわかるように, $O(m)$ のアルゴリズムと $O(m^2)$ のアルゴリズムは $m$ が大きくなると性能差がきわめて大きくなる. いわんや $O(m)$ と $O(2^m)$ の差はきわめて大きい. 上にしめした素因数分解のアルゴリズムは $O(2^m)$-アルゴリズムであり, これを元にした, GCD 計算ももちろん $O(2^m)$-アルゴリズムとなる. GCD 計算には, これとはくらべものにならないくらい早い $O(m)$ のアルゴリズムがある. これが, ユークリッドの互除法である.