アルゴリズムの効率と計算の限界 1 / 16

学ぶ > プログラミング > アルゴリズムの効率と計算の限界

アルゴリズムの効率と計算の限界

領域 (3) プログラミング学習指導要領 (3)ア(ア)(イ)

探索と整列の手間(比較の回数)、手間の増え方、組合せ爆発、近似で解く考え方

探索の手間

30 を探す(小さい順に並んだ 16 個のデータ)3162931241551862172482793010331136123913421445154816① まん中は 24。探す 30 は、24 より大きい → 右の半分へ② まん中は 36。探す 30 は、36 より小さい → 左へ③ まん中は 30。見つかった!303 回で見つかった(先頭から調べる線形探索なら、10 回)比べるたびに、探す範囲が半分になる。データが並んでいることが前提。

3 から 48 まで 3 ずつ増える 16 個の数が並び、30 を探す。まん中の 24、36、30 の順に比べて、探す範囲が半分ずつになり、3 回で見つかる。

二分探索は、まん中と比べて、探す範囲を半分にしていく。この例では、16 個の中から、3 回で見つかる。

同じ結果を出すアルゴリズムでも、手間(計算の回数)は大きく変わります。探したい値を見つける「探索(たんさく)」で比べてみます。

線形探索(せんけいたんさく)は、先頭から 1 つずつ調べます。データが n 個なら、最悪で n 回の比較が必要です。

二分探索(にぶんたんさく)は、データが小さい順(または大きい順)に並んでいることが前提です。まん中の値と比べて、探す範囲を半分に絞ることを繰り返します。

データの数 n線形探索(最悪)二分探索(最大)
100100 回7 回
1,0001,000 回10 回
1,000,0001,000,000 回20 回

ここが大事二分探索では、並んだデータが 1000 倍になっても、比較は 10 回ほどしか増えない。最大の回数は、おおよそ「2 を何回かけると n をこえるか」で、数え方によって 1 回ずれることがある。

整列の手間

データを小さい順に並べる「整列(せいれつ)」では、選択ソートやバブルソートのように 2 つずつ比べる方法があります。選択ソートやバブルソートでは、比較の回数は n × (n − 1) ÷ 2 回です(すべての組を 1 回ずつ比べる回数と同じです)。

データの数 n比較の回数(n × (n − 1) ÷ 2)
1045 回
1004,950 回
1,000499,500 回

ここが大事n が 10 倍になると、比較の回数はおよそ 100 倍になる(n の 2 乗に比例する)。

手間の増え方

データが増えたときの手間の増え方は、アルゴリズムによってちがいます。

手間の増え方n = 10n = 20n = 30
n に比例(1 つずつ調べる)102030
n の 2 乗に比例(n = 10 なら、n × n = 100)100400900
2 の n 乗(すべての組みあわせ)1,0241,048,5761,073,741,824

ここが大事「2 の n 乗」の形は、n が少し増えるだけで手間が爆発的に増える。

計算の限界

「すべての組みあわせを調べる」方法は、対象が増えると組みあわせの数が爆発的に増えます(組合せ爆発(くみあわせばくはつ))。たとえば、20 個のスイッチの入り切りの組みあわせは 2 の 20 乗で約 105 万通りです。

巡回セールスマン問題は、いくつかの都市を 1 度ずつ回って戻る、いちばん短い道すじを探す問題です。都市が 20 のとき、道すじは約 6 × 10 の 16 乗通りです(出発点を決め、逆回りを同じと数えた場合。逆回りを別に数えると 2 倍)。1 秒に 10 億通り調べても、約 2 年かかります。

このように、現実的な時間で答えが出せない問題もあります。そのときは、いちばんでなくてもじゅうぶんによい答えを短い時間で探す「近似(きんじ)」の考え方を使います。

ここが大事手間が爆発する問題は、完全な答えをあきらめて近い答えを探すことがある。

確認問題

答えを選ぶと、すぐに答え合わせと解説が出ます。すべて正解にすると、学んだしるしがつきます。 正解: 0 / 9

答えを選ぶと、派手な演出が出るよ!

演出ラボで、ほかの演出も、ためせます。

  1. 1,000 個のデータを先頭から 1 つずつ調べる線形探索(せんけいたんさく)で探す。最悪の場合、何回比べるか。

  2. 小さい順に並んだ 1,000 個のデータを、二分探索(にぶんたんさく)で探す。最大で何回ほど比べればよいか。

  3. 二分探索(にぶんたんさく)を使うために必要な条件はどれか。

  4. 100 個のデータをすべての組で比べて並べる方法で整列(せいれつ)する。比較の回数は n × (n − 1) ÷ 2 である。比較は何回か。

  5. 整列(せいれつ)の比較の回数は n × (n − 1) ÷ 2 回である。このとき、データの数が 10 倍になると、比較の回数はおよそ何倍になるか。

  6. 20 個のスイッチがそれぞれ「入」「切」のどちらかになる。入り切りの組みあわせは全部で何通りか。

  7. 1 万人の名簿が学籍番号の順に並んでいる。二分探索(にぶんたんさく)である番号の人を探すとき、最大でおよそ何回比べればよいか。

  8. 対象が増えると、「すべての組みあわせを調べる」方法がほとんど使えなくなる。その理由としてもっとも適切なものはどれか。

  9. 巡回セールスマン問題のように、完全な答えを求めると現実的な時間では終わらない問題がある。このような問題でよく使われる考え方はどれか。