金庫破りと計算量膨張
- n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 ～ 99 の 100 個の正解がありうるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。
99 が正解とは限らないので、平均的にはこれより早く解き終わります。 - 0 であるときの確率は 1/100 で、このときの手数は 1 手です。
- 1 であるときの確率は 1/100 で、このときの手数は 2 手です。
- 2 であるときの確率は 1/100 で、このときの手数は 3 手です。
- 3 であるときの確率は 1/100 で、このときの手数は 4 手です。
: - 99 であるときの確率は 1/100 で、このときの手数は 100 手です。
つまり、平均手数は 1/100 × 1 + 1/100 × 2 + 1/100 × 3 + … + 1/100 × 100 = 50.5 により、100 手目の約半分です。
- ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計算量といいます。正確な定義は後に譲ります。
- 試みに、n が大きくなったときに、 暗証ロックを開けるのに必要な最悪の手数 (worst-case complexity) を求めてみます。
| 問題の大きさ | n = 1 | n = 2 | n = 5 | n = 10 | n = 20 | n = 50 | n = 100 |
| 最悪の手数 | 10 手 | 100 手 | 105 手 | 1010 手 | 1020 手 | 1050 手 | 10100 手 |
あまり大したことないように思いますか? 1 秒間に 1 回の暗証番号を入力できる人がいたとして、 どのくらいかかるか計算してみましょうか。
| 問題の大きさ | n = 1 | n = 2 | n = 5 | n = 10 | n = 20 | n = 50 | n = 100 |
| 最悪の手数 | 10 手 | 100 手 | 105 手 | 1010 手 | 1020 手 | 1050 手 | 10100 手 |
| 手入力の時間 | 10 秒 | 100 秒 | 27.8 時間 | 316.9 年 | 3.16 兆年 | 2.11 × 1032 宙齢 | 2.11 × 1082 宙齢 |
※ 宙齢は、宇宙の塵から地球ができてこのかた現在までの年数 (150 億年) を表す単位 (出典: 山本芳嗣，久保幹雄「巡回セールスマン問題への招待」朝倉書店， ISBN: 978-4254126150 - 良書なのでぜひ読みましょう) 。
5 桁の暗証ロックと 10 桁の暗証ロックでは、 計算量が 2 倍どころではないのがわかりますか。 n が大きくなるにつれ、 計算量は 10n の割合で大きくなっていくわけです。 あとで説明しますが、n の指数時間で膨張するアルゴリズムは、 n がちょっとでも大きくなると、もう解くことが不可能です。 - 機械でオートダイヤルすればよさそうですか? では、 超高速のスーパーコンピュータで暗証入力をしてみましょうか。 第4世代の Core i7-4770K プロセッサ (3.8cm × 3.8cm) は、 1 秒間に 164,180,000,000 回の単純計算 (164.18GIPS) ができます。 地球の赤道半径は 6,378km なので、地球上におよそ 3.54 × 109 億個敷き詰めることができますから、 地球全体では 5.81 × 1019 ギガ回というとんでもない単純計算能力を持つことになります。 おまけして 6.0 × 1019 GIPS とし、 このスーパーコンピュータを使って 1 秒間に 60,000,000,000,000,000,000,000,000,000 回の暗証入力ができるものとしましょう。 これなら一瞬で解けそうですが、はたして...
| 問題の大きさ | n = 1 | n = 2 | n = 5 | n = 10 | n = 20 | n = 50 | n = 100 |
| 最悪の手数 | 10 手 | 100 手 | 105 手 | 1010 手 | 1020 手 | 1050 手 | 10100 手 |
| スパコンの時間 | 1.6 × 10-28 秒 | 1.6 × 10-27 秒 | 1.6 × 10-24 秒 | 1.6 × 10-19 秒 | 1.6 × 10-9 秒 | 3520 宙齢 | 3.52 × 1053 宙齢 |
※ 地球に敷き詰めるというとんでもないアイディアも、 山本芳嗣，久保幹雄「巡回セールスマン問題への招待」朝倉書店， ISBN: 978-4254126150 によります (良書なのでぜひ読みましょう) 。
n = 20 のときと n = 50 のとき (1.6 ナノ秒と 3520 宙齢) では、 まるきり計算時間が違うのがわかりますか? n = 100 のときはもう計算不能です (地球が 352,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 回くらい生まれ変わると計算がおわる) 。 これは、今後、Core i7 の速度が 10000 倍になったくらいでは
とうてい解決できるような問題ではないわけです。
多項式時間と指数時間，オーダ
- ところで、暗証番号の解読は普段よく見るダイヤル錠 (電話オペレータのお姉さんではない) 破りでも同じですが、 カギ屋さんはセサミロックデコーダという専用の道具 (特殊形状の金属板) を使い、 一瞬で開けてしまいます。
- セサミロックデコーダを使うと、番号の当たり，はずれが 1 桁ずつわかります。 各桁が 0 ～ 9 で 5 桁のダイヤルなら、 最悪 10 回の試行を 5 桁ぶん行えばよいので、 たかだか 50 回で正解がわかります。 先ほどの結果とあわせると、n 桁のダイヤル錠を手で開錠するための時間は、
| 問題の大きさ | n = 1 | n = 2 | n = 5 | n = 10 | n = 20 | n = 50 | n = 100 |
| セサミデコーダなし | 10 秒 | 100 秒 | 27.8 時間 | 316.9 年 | 3.16 兆年 | 2.11 × 1032 宙齢 | 2.11 × 1082 宙齢 |
| セサミデコーダあり | 10 秒 | 20 秒 | 50 秒 | 1 分 40 秒 | 3 分 20 秒 | 8 分 20 秒 | 16 分 40 秒 |
となります。n = 20 のときをみてみると、 解き方 (アルゴリズム) によって
まったく効率が違う のがわかると思います。
多項式時間と指数時間
- もういちど、セサミロックデコーダ (カギあけ道具) のあるときとないときの計算量を式でまとめてみましょうか。
| 計算量 |
| セサミデコーダなし | 10n |
| セサミデコーダあり | 10n |
10n と 10n は似てますが、 計算量はぜんぜん違います。前者を n の指数時間 (exponential time)，後者を多項式時間 (polynomial time) といいます。 - 多項式時間 (polynomial time) というのは、問題サイズを n としたとき、計算量が n に関する多次式 (たとえば n3 + 5n2 + 2n + 8) で表せるようなものをいいます。 多項式時間の「多項式」には、n 乗は含みません (それは指数時間に入る) 。また、「多項式」である必要はありません (単項式でもよい) 。
| [P1] | 4n5 + 7n3 + 9000 |
| [P2] | n3 + 5n2 + 2n + 8 |
| [P3] | 10n |
などはぜんぶ多項式時間のクラスに入ります。 - 指数時間 (exponential time) の問題というのは、問題サイズを n とするとき、計算時間が n の累乗になってしまうようなものをいいます。
| [E1] | 10n |
| [E2] | 5n + 8×2n |
| [E3] | n3 + 2×5n + 2n + 8 |
などはぜんぶ指数時間のクラスに入ります。 式自体が単項式か多項式かは関係ありませんので、 [E2] の例も指数時間クラスに含まれます。 ※ ちなみに、8×2n 自体も指数時間です。なぜなら実は 8×2n = 2(n + 3) だから。7×2n でも、 (n + 3) の 3 が小数になるだけで同じです。
[E3] は、(初項は多項式時間ですが) 第 2 項が指数時間なので、 式全体としては指数時間です (n が大きくなると、おもに 2×5n が爆発する) 。 ※ n ! も指数クラスです。Stirring の公式によれば、 n が大きいとき n ! = 2n π(1/2) nn e-n と近似されるからです。
計算量とオーダ
- 次に、計算量のオーダ (オーダー) という概念を勉強しましょう。
- 正確な定義は講義にゆずりますが、計算量のオーダというのは、 おおざっぱな計算量という程度の意味で、n の増大に対して計算量がどの割合で膨張するのかを示すものです。
- たとえば、[P1] の式 (4n5 + 7n3 + 9000) のオーダは n5 で、 O (n5) とあらわせます。 n が大きくなれば定数の 9000 は省略できるとしても、 7n3 も膨張するはずですし、省略していいんでしょうか? 実は (n が比較的小さい範囲を動く世界のみを扱うことがわかっている場合を除き) ぜんぜんオッケーです。
- まず、4n5 + 7n3 + 9000 という計算量の式において、仮に n = 100 とすると、
| 4n5 + 7n3 + 9000 | = | 40007009000 |
| 4n5 | = | 40000000000 |
と、もとの計算量に比べて -1.75% の誤差があります。が、 n が増大していき、仮に 10000 になったとすると、 7n3 以降がなくても | 4n5 + 7n3 + 9000 | = | 400000007000000009000 |
| 4n5 | = | 400000000000000000000 |
となります。4 と 7 の間の 0 が増えていますから、 当たり前ですが誤差は小さくなり、-0.0000000175% です。 n の増大を考えるとき、 次数の小さい項は無視できそう ですね。 - さて、しかし 4n5 の定数係数を取り去って、 n5 にまで簡略化してしまうのはいささか抵抗があります。
| 4n5 + 7n3 + 9000 | = | 400000007000000009000 |
| n5 | = | 100000000000000000000 |
にみられる 4:1 の比率は、この先 n がどんなに大きくなろうとも一定だからです。 しかし考えてみましょう。 2.11 × 1032 宙齢もかかる計算が、 たとえ 1/4 の計算量に減ったところでなにも変わらないですよね (計算量の桁が減るわけではないので) 。 ですから、 定数倍の係数も無視できそう です (あとで補足) 。
- 以上のことから、 4n5 + 7n3 + 9000 のオーダは O (n5) で表します。
- 工学ではあまり関係ないので補足ですが...
定数係数が重要になってくる議論もあり、 組み合わせ数学ではこれを区別することがあります (数学科ではそう習った) 。 そのときの記号には o (小文字) を使います。たとえば、 4n5 + 7n3 + 9000 のオーダは o (4n5) です。 これは、4n5 + 7n3 + 9000 の計算量はオーざっぱに 4n5、というていどの意味で、 私たちが使う大文字の O は、 4n5 + 7n3 + 9000 の計算量が、もっとオーざっぱに n5 である、というていどの意味です。
- 計算量というのはとっつきにくい概念だとは思いますが、 おぼろげにでも理解していただけたでしょうか。
この資料は複写自由です。