コンピュータIIL（情報科学入門）第11回

11.1 計算量

11.1.1 計算量とは

前回の話で、問題を解くアルゴリズムが存在すれば、その問題はチューリング機械などの計算機で解けることが分かりました。 しかし、一つの問題を解くアルゴリズムは一つとは限りません。 アルゴリズムを改良することによって、もっと速く問題が解ける可能性も出てきます。 例えば、低速アルゴリズムなら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倍になる（またはそれ以下）という傾向を表します。

11.1.2 計算量の例

それでは、具体的なアルゴリズムについて計算量を求めてみます。 ここで取り上げるのは、整列アルゴリズムです。 整列 （ sorting ） とは、与えられた数列を小さい順に並び替えることです。

整列では、与えられた数列の長さを入力のサイズと見なすのが妥当です。 また、整列の最も本質的な基本操作は、2つの数を比較することですので、比較の回数を計算時間と見なすことにします。

最初に紹介するアルゴリズムは、 選択整列 （ selection sort ） です。 これは次のような整列法です。 まず、全体の最小要素を探して、これと第1要素を交換します。 次に、残りの中から最小要素を探して、これと第2要素を交換します。 この手続きを繰り返し、残りが1つになったら終了します。

選択整列法は、数列の長さが同じならば、同じ回数だけ比較します。 したがって、最悪計算量と平均計算量は同じになります。

n 個の数の中から最小要素を見つけるには、 n - 1 回の比較が必要です。 したがって、全体の比較回数は

となります。

と考えますと、選択整列法の比較回数 T ( n ) は

となります。

n = 100 を基準とし、この2倍、3倍、…、8倍について T ( n ) の比率を計算すると、次のようになります。

入力のサイズが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.

入力のサイズが2倍、3倍、4倍…になると、比較回数はほぼ4倍、9倍、16倍…になるので、計算量は O ( n ^ 2) であることが確かめられる。

11.1.3 手に負えない問題

O (2 ^ n ) という計算量は、計算時間が急激に増大します。 T ( n ) = 2 ^ n の場合、たとえ基本操作が1000分の1秒で実行できましても、 n = 50 で何万年も掛かってしまいます。

計算量が O (2 ^ n ) のアルゴリズムしかない問題は、 手に負えない問題 （ intractable problem ） と呼ばれます。 手に負えない問題は、事実上、計算機で解けない問題と考えるべきです。

11.2 演習11

挿入整列法の平均的な比較回数 T ( n ) が

であることに基づいて、挿入整列法の平均計算量が O ( n ^ 2) であることを確認してください。 n = 100 を基準とし、この2倍、3倍、…、8倍について、 T ( n ) の比率を計算します。

なお、Microsoft Excelなどの表計算ソフトが得意な人は、ソフトを利用して計算してもかまいません。

11.3 レポート課題

今日の演習11の答案をメールで送信してください。 メールの差出人は学内のアドレス（b04a001@twcu.ac.jpなど）とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（12月22日）を明記してください。

11.4 参考文献

• R. Sedgewick: Algorithms in C, Addison-Wesley, 1990. 野下浩平（他訳）『アルゴリズムC』近代科学社、1996.
• 長尾真（他編集）『岩波情報科学辞典』岩波書店、1990.