計算量

例 14.1   整数 $n$ の素数判定には自明な方法がある.

• 2, 3, $\ldots$, $n-1$ で割ってみる.
• 2, 3, $\ldots$, $\lfloor \sqrt{n} \rfloor$ で割ってみる. ( $\lfloor x \rfloor$ は $x$ を越えない最大の整数.)
• 2 以外は奇数で割る.

いずれにせよ $\sqrt{n}$ に比例する回数の割算が必要である. たとえば $n \simeq 2^{1024} \simeq 10^{308}$ のとき, $\sqrt{n} \simeq 2^{512} \simeq 10^{154}$. 現在の一般的な CPU の クロックは 1GHz ($10^9$Hz) 程度, すなわち単位操作を一秒間に $10^9$ 回できる程度なので, 1クロックで1回割算ができても $10^{145}$ 秒 $\simeq 3.17 \times 10^{137}$ 年程かかることになる.

$2^{1024}$ 程度の数の素因数分解は, もっとよいアルゴリズム を用いても困難であり, それが RSA 暗号の安全性の根拠となって いるが, そもそもアルゴリズムの「よい」「よくない」は何で計れば いいのだろうか. その尺度が計算量 (complexity) と呼ばれる概念である.

素朴には, 計算量とは, ある大きさのデータに対して, 計算にどれだけ 時間 (ステップ数) あるいは領域 (メモリ量) がかかるかを示す量である. ここでいくつか曖昧な点がある.

• データの大きさ
  • 大きな数も小さな数も一つの数と見る
  • メモリ上で必要な量を単位とする.

• 1 ステップとは
  • 数の計算は 1 ステップと見る.
  • 計算機の命令を 1 ステップと見る.

例えば浮動小数演算を用いる場合には, どちらで考えても同じだが, 近似なしに正確な値を有理数で求めていく場合には注意が必要である.

例 14.2   2 つの $n$ 桁の整数

$$a = \sum_{i=0}^{n-1} a_i\cdot 10^i, \quad b = \sum_{i=0}^{n-1} b_i\cdot 10^i$$

を筆算の要領で計算することを考える.

$$ab = \sum_{i=0}^{n-1} ab_i\cdot 10^i$$

を使って, $ab_i$ を計算してから $i$ 桁左にシフトしながら足して 行く. 一桁の数 $u$ に対し $au = \sum_{i=0}^n m_i\cdot 10^i$ を計算するアルゴリズムは次の通り.

$c \leftarrow 0$


for ( $i = 0$; $i < n$; $i$++ )

		 $t \leftarrow a_ib+c$

		 $m_i \leftarrow t \bmod 10$

		 $c \leftarrow \lfloor t/10 \rfloor$


end for

$m_n \leftarrow c$

この計算で, かけ算は $n$ 回, 10 による割算が $n$ 回必要である.

次に, $ab_i$ をシフトして足していく計算を考える. これは, 繰り上がりを無視すれば $n$ 桁の数 $\sum_{i=0}^n f_i\cdot 10^i$, $\sum_{i=0}^n g_i\cdot 10^i$ の加算と考えてよいから次のアルゴリズムで計算できる.

$c = 0$


for ( $i = 0$; $i < n$; $i$++ )

		 $t \leftarrow f_i+g_i+c$


if $t \ge 10$ $f_i \leftarrow t-10$, $c \leftarrow 1$


else $f_i \leftarrow t$, $c \leftarrow 0$


end for

(繰り上がりの処理)

これは, 本質的には加算が $n$ 回で計算できる. 以上の計算が $n$ 回必要になるから, $n$ 桁の数の積の計算には $n^2$ に比例するステップ数が必要になることが分かる.