O-記法

アルゴリズムの効率を見る場合, データの大きさが大きくなる時の 漸近的な計算量のふるまいがしばしば重要となる. 解析で習ったのと 同じ記号を使って, ある関数 $M(n)$, $f(n)$ に対し, $M(n)/f(n)$ が $n\rightarrow \infty$ の時有界なら $M(n)$ は高々 $O(f(n))$ であるという.

例 14.3   $M(n)$ が $n$ の $k$ 次式なら $M(n)$ は $O(n^k)$.

例 14.4   ある正数 $c$, $a$ が存在して, $M(n) > c e^{an}$ なら, 全ての $k$ に対して $M(n)$ は $O(n^k)$ でない.

例 14.5   $M(n)$ が $O(\log n)$ なら $M(n)/n \rightarrow 0$ ( $n\rightarrow \infty$).

例 14.6   $n$ 桁の整数を二つかける筆算アルゴリズムの計算量は $O(n^2)$.

次に, 高速アルゴリズムの例として, Karatsuba アルゴリズムを紹介する. まず, 二桁の数 $a = a_1\cdot 10+a_0$ $b = b_1\cdot 10+b_0$ の積を考える. 普通にやると

$$ab = a_1b_1 \cdot 10^2 + (a_1b_0+a_0b_1) \cdot 10 + a_0b_0$$

とかけ算が 4 回現れる. これを

$$ab = a_1b_1 \cdot 10^2 + ((a_1-a_0)(b_0-b_1)+a_1b_1+a_0b_0) \cdot 10 + a_0b_0$$

と変形するとかけ算は $a_1b_1$, $a_0b_0$, $(a_1-a_0)(b_0-b_1)$ の 3 回になる. (加算は増える.) これを繰り返す. $2^n$ 桁の整数 $a$, $b$ をかける場合 の計算量を $T(2^n)$ とする.$N = 2^{n-1}$ として $a = a_1\cdot 10^N+a_0$, $b = b_1\cdot 10^N+b_0$, $0 \le a_i, b_i \le 10^N$ と書いて, 上の考察を適用する. 一桁の乗算, 加減算のコストをそれぞれ $M$, $A$ とすると,

$$T(2^n) = 3T(2^{n-1})+4\cdot 2^nA.$$

(第 2 項は「倍長」整数の加算コストを表す. $T(1)=M$ より, この漸化式を解いて,

$$T(2^n) = (M+8A)\cdot 3^n-8A\cdot 2^n.$$

よって, $T(2^n) = O(3^m)$. これより

$$T(n) = O(3^{\log_2 n}) = O(n^{\log_2 3}).$$

$\log_2 3 \simeq 1.58$ より 漸近的には筆算よりよいアルゴリズムと言える.

注意 14.1   一変数多項式の積でも同じアルゴリズムが使える. かなり低い次数 (20 次程度) から, 通常の $O(n^2)$ アルゴリズムより高速になる.

注意 14.2   実は $O(n\log n)$ アルゴリズムがある. (FFT; Fast Fourier Transform)

演習 14.1   $n$ 次正方行列の積の計算量は?

例 14.7   (互除法の計算量) $a_0(=n)$ 桁, $a_1$ 桁 ($a_0 \ge a_1$) の 2 整数の GCD を互除法で 計算して,

$$a_0 \ge a_1 > a_2 > \ldots > a_k$$

である桁数 $a_i$ を持つ数列が得られたとする. このとき, $m$ 桁の数 を $l$ 桁の数で割ってあまりを求める操作のコストを $l(m-l)$ と見積もる と, 互除法のコストは

$$C = a_1(a_0-a_1)+a_2(a_1-a_2)+\ldots + a_{k-1}(a_{k-2}-a_{k-1})$$

と見積もれる.

$$\begin{eqnarray*} C &=& a_0a_1+\ldots + a_{k-2}a_{k-1}-(a_1^2+\ldots +a_{k-1}^2)... ...})^2) +{1 \over 2}(a_0^2-a_{k-1}^2)\\ & \le& {1 \over 2} a_0^2 \end{eqnarray*}$$

よって, 互除法の計算量は高々 $O(n^2)$. 実際に, フィボナッチ数列の 隣あう 2 項がこの計算量を実現する. (つまり最悪) これは, おおざっぱ にいえば

$$F_n > F_{n-1} > \ldots$$

で, $F_n = F_{n-1}+F_{n-2}$ より, $F_n$, $F_{n-1}$ から互除法で 生成される数列は $F_{n-2}$, $F_{n-3}$ $\ldots$ であることから でる. 詳しくは http://www.math.kobe-u.ac.jp/noro/main/node33.html 参照.

演習 14.2   glib_ 関数を使って GCD の計算時間をプロットしてみる. 横軸に桁数, 縦軸に計算時間をとる. 各桁数に対し, その桁数の 整数を 2 つ生成して, GCD の計算を繰り返す. 必要な機能は次の通り.

1. 乱数発生 : lrandom(N)

   2 進数で $N$ ビットの整数 $x$ ( $0 \le x \le 2^{\tt N}-1$) をランダムに発生する.

2. 時間計測 : time()[0]

   その時点までの計算時間 (CPU 時間) を返す. 次のようなプログラム により, 必要な部分の計算時間を計測できる.

   
   T0 = time()[0];
   /* 1 回ではばらつきが生ずるので繰り返す	*/
   for ( I = 0; I < 10; I++ )
       int_gcd(A,B);
   T1 = time()[0];
   TIme = T1-T0;