| 目次 | 索引 |
|---|---|
h2 計算量 toc-complexity
h3 計算量とは toc-what-is-complexity
前回の話で、問題を解くアルゴリズムが存在すれば、
その問題はチューリング機械などの計算機で解けることが分かりました。
しかし、一つの問題を解くアルゴリズムは一つとは限りません。
アルゴリズムを改良することによって、
もっと速く問題が解ける可能性も出てきます。
例えば、低速アルゴリズムなら 100 万年も掛かる問題も、
高速アルゴリズムなら 0.1 秒で解けるといった具合です。
アルゴリズムの速さの目安となるのが
index 計算量 computational complexity けいさんりよう
です。
計算量は、入力のサイズが大きくなると、
それに応じて計算時間がどう増えるかという傾向を表します。
ただし、同じサイズでも、入力によって計算時間が変わるのが普通です。
最も時間の掛かる入力についての計算量を
index 最悪計算量 worst case complexity さいあくけいさんりよう
と呼びます。
平均的な入力についての計算量を
index 平均計算量 average case complexity へいきんけいさんりよう
と呼びます。
一般的に、計算量は
index 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) は、入力サイズが一つ大きくなると、
計算時間はだいたい 2 倍になる (またはそれ以下) という傾向を表します。
h3 計算量の例 toc-sorting-examples
それでは、具体的なアルゴリズムについて計算量を求めてみます。
ここで取り上げるのは、整列アルゴリズムです。
index 整列 sorting せいれつ
とは、与えられた数列を小さい順に並び替えることです。
整列では、与えられた数列の長さを入力のサイズと見なすのが妥当です。
また、整列の最も本質的な基本操作は、2 つの数を比較することですので、
比較の回数を計算時間と見なすことにします。
最初に紹介するアルゴリズムは、
index 選択整列 selection sort せんたくせいれつ
です。
これは次のような整列法です。
まず、全体の最小要素を探して、これと第 1 要素を交換します。
次に、残りの中から最小要素を探して、これと第 2 要素を交換します。
この手続きを繰り返し、残りが 1 つになったら終了します。
選択整列法は、数列の長さが同じならば、同じ回数だけ比較します。
したがって、最悪計算量と平均計算量は同じになります。
n 個の数の中から最小要素を見つけるには、n - 1 回の比較が必要です。
したがって、全体の比較回数は
(n - 1) + (n - 2) + ... + 1
となります。
n - 1 n - 2 ... 1 (元の足し算)
+ 1 2 ... n - 1 (逆の足し算)
------------------------------------
n n ... n
と考えますと、選択整列法の比較回数 T(n) は
T(n) = n * (n - 1) / 2
となります。
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) であることが分かります。
次に紹介するのは
index 挿入整列 insertion sort そうにゆうせいれつ
です。
これは次のような整列法です。
まず、第 1 要素のみが整列済みと見なします。
次に、整列済みの部分を右から左に見ていき、第 2 要素を挿入します。
そして、整列済みの部分を右から左に見ていき、第 3 要素を挿入します。
この手続きを繰り返し、全体が整列済みになったら終了します。
なお、負の無限大という第 0 要素を仮定しますと、
左に行き過ぎることはありません。
挿入整列法は、だいたい整列されている数列に対しては高速に整列します。
最悪の入力は、大きい順になっているものです。
最悪の場合、第 k 要素を挿入するには k 回比較します。
したがって、全体の比較回数は、
2 + 3 + ... + n
となります。
挿入整列法の最悪の場合の比較回数 T(n) は
T(n) = (n + 2) * (n - 1) / 2
となります。
例題 1.
挿入整列法の最悪の場合の比較回数 T(n) が
T(n) = (n + 2) * (n - 1) / 2
であることに基づいて、
挿入整列法の最悪計算量が 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) であることが確かめられる。
h3 手に負えない問題 toc-intractable-problems
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) のアルゴリズムしかない問題は、
index 手に負えない問題 intractable problem てにおえないもんたい
と呼ばれます。
手に負えない問題は、事実上、計算機で解けない問題と考えるべきです。
h2 演習 11 toc-exercises
挿入整列法の平均的な比較回数 T(n) が
T(n) = (n + 4) * (n - 1) / 4
であることに基づいて、
挿入整列法の平均計算量が O(n^2) であることを確認してください。
n = 100 を基準とし、この 2 倍、3 倍、…、8 倍について、
T(n) の比率を計算します。
なお、Excel などの表計算ソフトが得意な人は、
ソフトを利用して計算してもかまいません。
今日の演習11の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（12月10日）を明記してください。