学ぶ > プログラミング > アルゴリズムの効率と計算の限界
アルゴリズムの効率と計算の限界
領域 (3) プログラミング学習指導要領 (3)ア(ア)(イ)
探索と整列の手間(比較の回数)、手間の増え方、組合せ爆発、近似で解く考え方
上にスワイプして、つぎへ横にスクロールして、つぎへ (矢印キーも使えます)
探索の手間
3 から 48 まで 3 ずつ増える 16 個の数が並び、30 を探す。まん中の 24、36、30 の順に比べて、探す範囲が半分ずつになり、3 回で見つかる。
同じ結果を出すアルゴリズムでも、手間(計算の回数)は大きく変わります。探したい値を見つける「探索」で比べてみます。
線形探索は、先頭から 1 つずつ調べます。データが n 個なら、最悪で n 回の比較が必要です。
二分探索は、データが小さい順(または大きい順)に並んでいることが前提です。まん中の値と比べて、探す範囲を半分に絞ることを繰り返します。
| データの数 n | 線形探索(最悪) | 二分探索(最大) |
|---|---|---|
| 100 | 100 回 | 7 回 |
| 1,000 | 1,000 回 | 10 回 |
| 1,000,000 | 1,000,000 回 | 20 回 |
ここが大事二分探索では、並んだデータが 1000 倍になっても、比較は 10 回ほどしか増えない。最大の回数は、おおよそ「2 を何回かけると n をこえるか」で、数え方によって 1 回ずれることがある。
整列の手間
データを小さい順に並べる「整列」では、選択ソートやバブルソートのように 2 つずつ比べる方法があります。選択ソートやバブルソートでは、比較の回数は n × (n − 1) ÷ 2 回です(すべての組を 1 回ずつ比べる回数と同じです)。
| データの数 n | 比較の回数(n × (n − 1) ÷ 2) |
|---|---|
| 10 | 45 回 |
| 100 | 4,950 回 |
| 1,000 | 499,500 回 |
ここが大事n が 10 倍になると、比較の回数はおよそ 100 倍になる(n の 2 乗に比例する)。
手間の増え方
データが増えたときの手間の増え方は、アルゴリズムによってちがいます。
| 手間の増え方 | n = 10 | n = 20 | n = 30 |
|---|---|---|---|
| n に比例(1 つずつ調べる) | 10 | 20 | 30 |
| n の 2 乗に比例(n = 10 なら、n × n = 100) | 100 | 400 | 900 |
| 2 の n 乗(すべての組みあわせ) | 1,024 | 1,048,576 | 1,073,741,824 |
ここが大事「2 の n 乗」の形は、n が少し増えるだけで手間が爆発的に増える。
計算の限界
「すべての組みあわせを調べる」方法は、対象が増えると組みあわせの数が爆発的に増えます(組合せ爆発)。たとえば、20 個のスイッチの入り切りの組みあわせは 2 の 20 乗で約 105 万通りです。
巡回セールスマン問題は、いくつかの都市を 1 度ずつ回って戻る、いちばん短い道すじを探す問題です。都市が 20 のとき、道すじは約 6 × 10 の 16 乗通りです(出発点を決め、逆回りを同じと数えた場合。逆回りを別に数えると 2 倍)。1 秒に 10 億通り調べても、約 2 年かかります。
このように、現実的な時間で答えが出せない問題もあります。そのときは、いちばんでなくてもじゅうぶんによい答えを短い時間で探す「近似」の考え方を使います。
ここが大事手間が爆発する問題は、完全な答えをあきらめて近い答えを探すことがある。
-
1,000 個のデータを先頭から 1 つずつ調べる線形探索で探す。最悪の場合、何回比べるか。
-
小さい順に並んだ 1,000 個のデータを、二分探索で探す。最大で何回ほど比べればよいか。
-
二分探索を使うために必要な条件はどれか。
-
100 個のデータをすべての組で比べて並べる方法で整列する。比較の回数は n × (n − 1) ÷ 2 である。比較は何回か。
-
整列の比較の回数は n × (n − 1) ÷ 2 回である。このとき、データの数が 10 倍になると、比較の回数はおよそ何倍になるか。
-
20 個のスイッチがそれぞれ「入」「切」のどちらかになる。入り切りの組みあわせは全部で何通りか。
-
1 万人の名簿が学籍番号の順に並んでいる。二分探索である番号の人を探すとき、最大でおよそ何回比べればよいか。
-
対象が増えると、「すべての組みあわせを調べる」方法がほとんど使えなくなる。その理由としてもっとも適切なものはどれか。
-
巡回セールスマン問題のように、完全な答えを求めると現実的な時間では終わらない問題がある。このような問題でよく使われる考え方はどれか。
確認問題の正解: 0 / 9