前回の話で、問題を解くアルゴリズムが存在すれば、その問題はチューリング機械などの計算機で解けることが分かりました。 しかし、一つの問題を解くアルゴリズムは一つとは限りません。 アルゴリズムを改良することによって、もっと速く問題が解ける可能性も出てきます。 例えば、低速アルゴリズムなら100万年も掛かる問題も、高速アルゴリズムなら0.1秒で解けるといった具合です。
アルゴリズムの速さの目安となるのが 計算量 ( computational complexity ) です。 計算量は、入力のサイズが大きくなると、それに応じて計算時間がどう増えるかという傾向を表します。 ただし、同じサイズでも、入力によって計算時間が変わるのが普通です。 最も時間の掛かる入力についての計算量を 最悪計算量 ( worst case complexity ) と呼びます。 平均的な入力についての計算量を 平均計算量 ( average case complexity ) と呼びます。
一般的に、計算量は O 記法 ( O-notation ) と呼ばれる表記法で表現されます。 重要な計算量は、 O (1), O ( n ), O ( n ^ 2), O ( n ^ 3), O (2 ^ n ) などです。
計算量 O (1) は、入力サイズが大きくなっても、計算時間はだいたい一定(またはそれ以下)という傾向を表します。
計算量 O ( n ) は、入力サイズが大きくなると、計算時間はだいたいそれに比例する(またはそれ以下)という傾向を表します。
計算量 O ( n ^ 2) は、入力サイズが大きくなると、計算時間はだいたいその2乗に比例する(またはそれ以下)という傾向を表します。
計算量 O ( n ^ 3) は、入力サイズが大きくなると、計算時間はだいたいその3乗に比例する(またはそれ以下)という傾向を表します。
計算量 O (2 ^ n ) は、入力サイズが1つ大きくなると、計算時間はだいたい2倍になる(またはそれ以下)という傾向を表します。
それでは、具体的なアルゴリズムについて計算量を求めてみます。 ここで取り上げるのは、整列アルゴリズムです。 整列 ( sorting ) とは、与えられた数列を小さい順に並び替えることです。
整列では、与えられた数列の長さを入力のサイズと見なすのが妥当です。 また、整列の最も本質的な基本操作は、2つの数を比較することですので、比較の回数を計算時間と見なすことにします。
最初に紹介するアルゴリズムは、 選択整列 ( selection sort ) です。 これは次のような整列法です。 まず、全体の最小要素を探して、これと第1要素を交換します。 次に、残りの中から最小要素を探して、これと第2要素を交換します。 この手続きを繰り返し、残りが1つになったら終了します。
選択整列法は、数列の長さが同じならば、同じ回数だけ比較します。 したがって、最悪計算量と平均計算量は同じになります。
n 個の数の中から最小要素を見つけるには、 n - 1 回の比較が必要です。 したがって、全体の比較回数は
となります。
n - 1 | n - 2 | ... | 1 | (元の足し算) | |
+ | 1 | 2 | ... | n - 1 | (逆の足し算) |
----- | ----- | ----- | ----- | ----- | |
n | n | ... | n |
と考えますと、選択整列法の比較回数 T ( n ) は
となります。
n = 100 を基準とし、この2倍、3倍、…、8倍について T ( n ) の比率を計算すると、次のようになります。
n | T(n) | 比率 |
---|---|---|
100 | 4950 | 1.00 |
200 | 19900 | 4.02 |
300 | 44850 | 9.06 |
400 | 79800 | 16.12 |
500 | 124750 | 25.20 |
600 | 179700 | 36.30 |
700 | 244650 | 49.42 |
800 | 319600 | 64.57 |
入力のサイズが2倍、3倍、4倍…になると、比較回数はほぼ4倍、9倍、16倍…になるので、計算量は O ( n ^ 2) であることが分かります。
次に紹介するのは 挿入整列 ( insertion sort ) です。 これは次のような整列法です。 まず、第1要素のみが整列済みと見なします。 次に、整列済みの部分を右から左に見ていき、第2要素を挿入します。 そして、整列済みの部分を右から左に見ていき、第3要素を挿入します。 この手続きを繰り返し、全体が整列済みになったら終了します。 なお、負の無限大という第0要素を仮定しますと、左に行き過ぎることはありません。
挿入整列法は、だいたい整列されている数列に対しては高速に整列します。 最悪の入力は、大きい順になっているものです。
最悪の場合、第 k 要素を挿入するには k 回比較します。 したがって、全体の比較回数は、
となります。 挿入整列法の最悪の場合の比較回数 T ( n ) は
となります。
例題1. 挿入整列法の最悪の場合の比較回数 T ( n ) が
であることに基づいて、挿入整列法の最悪計算量が O ( n ^ 2) であることを確認してください。 n = 100 を基準とし、この2倍、3倍、…、8倍について、 T ( n ) の比率を計算します。
解答例1.
n | T(n) | 比率 |
---|---|---|
100 | 5049 | 1.00 |
200 | 20099 | 3.98 |
300 | 45149 | 8.94 |
400 | 80199 | 15.88 |
500 | 125249 | 24.81 |
600 | 180299 | 35.71 |
700 | 245349 | 48.59 |
800 | 320399 | 63.46 |
入力のサイズが2倍、3倍、4倍…になると、比較回数はほぼ4倍、9倍、16倍…になるので、計算量は O ( n ^ 2) であることが確かめられる。
O (2 ^ n ) という計算量は、計算時間が急激に増大します。 T ( n ) = 2 ^ n の場合、たとえ基本操作が1000分の1秒で実行できましても、 n = 50 で何万年も掛かってしまいます。
n | 2 ^ n | 時間 |
---|---|---|
10 | 1024 | 1.02秒 |
20 | 1048576 | 17.5分 |
30 | 1073741824 | 12.4日 |
40 | 1099511627776 | 34.8年 |
50 | 1125899906842624 | 35700年 |
計算量が O (2 ^ n ) のアルゴリズムしかない問題は、 手に負えない問題 ( intractable problem ) と呼ばれます。 手に負えない問題は、事実上、計算機で解けない問題と考えるべきです。
挿入整列法の平均的な比較回数 T ( n ) が
であることに基づいて、挿入整列法の平均計算量が O ( n ^ 2) であることを確認してください。 n = 100 を基準とし、この2倍、3倍、…、8倍について、 T ( n ) の比率を計算します。
なお、Microsoft Excelなどの表計算ソフトが得意な人は、ソフトを利用して計算してもかまいません。
今日の演習11の答案をメールで送信してください。 メールの差出人は学内のアドレス(b04a001@twcu.ac.jpなど)とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日(12月16日)を明記してください。