第3章 コンピュータとプログラミング
アルゴリズムの比較(効率)
同じ問題を解く手順(アルゴリズム)がいくつもあるとき、どれがよいかを比べる考え方を学びます。比較や計算の回数で比べること、データが増えたときの回数の増え方(計算量の考え方)が分かります。
説明
1. 同じ問題でも、手順はいくつもある
「1 から 100 までの合計」を求めるとき、1つずつ足していけば足し算が100回要ります。でも、端から組にすると、1 + 100、2 + 99、… とどの組も 101 になり、それが50組あるので、式1つで計算できます。
答えは同じ 5050 でも、手間はまったく違います。同じ問題を解くアルゴリズムはいくつもあり、手間(効率)が違うのです。
- (01)
goukei = 0 - (02)
i を 1 から 100 まで 1 ずつ増やしながら繰り返す: - (03)
goukei = goukei + i - (04)
表示する(goukei, " ", (1 + 100) * 100 ÷ 2)
表示:5050 5050
2. 時間ではなく「回数」で比べる
かかった時間で比べると、速いコンピュータを使っただけで結果が変わってしまいます。そこで、比較や計算などの基本の操作を何回するかで比べます。回数ならコンピュータに関係なく同じです。
回数は、データの並び方で変わることがあります。8個のデータの線形探索なら、探す値が先頭にあれば1回、最後なら8回です。どんな場合でも間に合うように、普通は一番多いときで比べます。
3. データが増えると、回数はどう増える?
カードが5枚なら、どんな方法で並べても大差ありません。でも1万枚、100万枚になると、方法によって手間がまったく違ってきます。
下のグラフは、データの数 n が増えたときの回数です。式で計算する方法はずっと同じ回数、二分探索はほとんど増えません。線形探索は n に比例してまっすぐ増え、選択ソートなどの並べかえ(n(n−1)/2)は、n が大きくなるほど急に増えます。

4. データを2倍にすると
増え方の違いは、データを2倍にしてみるとよく分かります。線形探索は2倍、選択ソートの比較は約4倍(2 × 2)、二分探索は1回増えるだけです。
データの数に対して回数がどう増えるかを、計算量(けいさんりょう)と呼びます。「比例して増える」「2乗に近い増え方をする」のように言い表します。
比べるのは回数そのものより「データが増えたときの増え方」。
5. 回数を時間に直してみる
1秒間に100万回比べられるコンピュータで、データの数を変えてみましょう。100万個を選択ソートで並べると、比較だけで約5.8日かかります。線形探索は1秒、二分探索は一瞬です。
コンピュータが速くなっても、増え方の大きいアルゴリズムは、データが増えるとすぐに追いつかなくなります。だから、手順の工夫が大切なのです。
比較の回数だけを数えた目安です(実際には、代入などほかの操作の時間もかかります)。
6. どれがよいかは場合による
回数が少ないアルゴリズムが、いつも一番よいとは限りません。二分探索は、先に並べかえておく手間がかかります。1回だけ探すなら、並べかえずに線形探索をした方が手間は少なくなります。
並べかえでも、クイックソートは普通とても速いのですが、並び方によっては遅くなることがあります。データの数・並び方・何回使うかを考えて選びます。
7. プログラムから回数を数える
共通テストでは、プログラムのある行が何回実行されるかを考える問題が出ることがあります。二重の繰り返しでは、外側の1回ごとに内側が何回まわるかを書き出して足します。
下のプログラムは、i が 0 のとき内側が5回、1 のとき4回、… とまわります。合計 5 + 4 + 3 + 2 + 1 = 15 回で、6個のデータの選択ソートの比較の回数と同じです。
ひとことで言うと回数で比べ、データが増えたときの回数の増え方で効率を見る。
例題
例題1 探索の回数を比べる
小さい順に並んだ 64個のデータから値を探します。線形探索と二分探索で、比較の回数は一番多くてそれぞれ何回ですか。データが 128個になったらどうですか。
- 線形探索は、一番多いときデータの数と同じなので 64回。128個なら 128回(2倍)。
- 二分探索は、1回ごとに残りが半分になります。64 → 32 → 16 → 8 → 4 → 2 → 1 と6回で1個に絞り、その1個と比べて 7回。
- 128個なら、最初の1回で64個に絞れるので、1回増えて 8回。データが2倍になっても1回しか増えません。
| データの数 | 線形探索 | 二分探索 |
|---|---|---|
| 64 | 64 | 7 |
| 128 | 128 | 8 |
例題2 二重の繰り返しの回数
次のプログラムで表示される数はいくつですか。また、1行目を n = 10 にすると、表示される数は何倍になりますか。
- (01)
n = 5 - (02)
kaisu = 0 - (03)
i を 1 から n まで 1 ずつ増やしながら繰り返す: - (04)
j を 1 から n まで 1 ずつ増やしながら繰り返す: - (05)
kaisu = kaisu + 1 - (06)
表示する(kaisu)
- 外側の i が 1 から 5 まで5回まわり、その1回ごとに内側の j も 1 から 5 まで5回まわります。
- kaisu = kaisu + 1 は 5 × 5 = 25回実行されるので、25 が表示されます。
- n = 10 にすると 10 × 10 = 100回。25回の 4倍です。n が2倍になると、回数は 2 × 2 = 4倍(2乗の増え方)になります。
練習
さわってみよう
並べかえ:並び方で回数は変わる?
同じ8個のデータを、選択ソートとバブルソートで同時に並べかえます。「逆順」「並んでいる」に切りかえて、比較と入れかえの回数がどう変わるか確かめましょう。「最後まで」を押すと回数だけすぐ見られます。
比較の回数は、どの並びでも28回(8 × 7 ÷ 2)で変わりません。入れかえの回数は並び方で変わり、「並んでいる」ではどちらも0回、「逆順」ではバブルソートが28回、選択ソートは4回です。
探索:15個から1つ探す
小さい順に並んだ15個のデータです。探す値を変えて、線形探索と二分探索の回数を比べましょう。60 はデータにない値です。
15個なら、二分探索はどの値でも4回以内です。線形探索は、85 や 60 のとき15回かかります。
やってみよう(共通テスト形式)
このサイトで作った問題です(過去の試験問題ではありません)。
生徒会の D さんは、アンケートの回答に同じ生徒番号が2回以上入っていないかを調べたい。次の2つの方法を考えた。
方法A:すべての2つの組について、番号が同じかどうかを比べる。
方法B:先に番号を小さい順に並べかえ、となりどうしだけを比べる。
方法Aをプログラムにすると、次のようになった。配列の添字は 0 から始まる。
(01) Bangou = [12, 7, 31, 7, 20] (02) kaisu = 0 (03) onaji = 0 (04) i を 0 から 要素数(Bangou) - 2 まで 1 ずつ増やしながら繰り返す: (05) j を i + 1 から 要素数(Bangou) - 1 まで 1 ずつ増やしながら繰り返す: (06) kaisu = kaisu + 1 (07) もし Bangou[i] == Bangou[j] ならば: (08) onaji = onaji + 1 (09) 表示する(onaji, " ", kaisu)
この単元が出た過去問の解説
ちょっと寄り道:豆知識・こぼれ話
試験に出るとはかぎりませんが、知っていると情報がもっと面白くなる話です。
都市が20になると、道順は約6京通り
いくつかの都市を1回ずつ回って出発点に戻るとき、一番短い道順を求める問題を「巡回セールスマン問題」といいます。すべての道順を調べると、都市が n 個のとき、道順は (n−1)!÷2 通りです(逆回りは同じとみなします)。
5都市なら12通りですが、10都市で181,440通り、20都市では約6京(6×1016)通りになります。1秒に10億通り調べられるコンピュータでも、20都市で約2年かかる計算です。データが増えたときに回数がどう増えるかが、どれほど大事かが分かります。
参考:(n−1)!÷2 の計算(19!÷2=60,822,550,204,416,000)
100万ドルの懸賞がかかった問題
「答えが正しいかを確かめるのは速くできる問題なら、答えを見つけるのも速くできるのか」という問題を「P対NP問題」といい、まだだれも解いていません。
アメリカのクレイ数学研究所は2000年、この問題を7つの「ミレニアム懸賞問題」の1つに選び、解いた人に100万ドルを出すとしています。巡回セールスマン問題(ある長さ以下で回れる道順があるかを問う形)は、この問題と深く関わる代表的な問題です。計算の回数の増え方を考えることは、数学の大きななぞにもつながっているのです。
参考:クレイ数学研究所 “Millennium Prize Problems”/同 “P vs NP”
わからなかったら、ここへもどる
- 探索(線形探索・二分探索)
- 整列(並べかえ)
- 中学数学「比例」「2乗に比例する関数」準備中
あわせて読む
次はこれ
先生・おうちの方へ
つまずきやすい所:①「速いアルゴリズム」を「速いコンピュータ」と混同する。②データが増えたときの増え方(比例・2乗・2倍で1回増える)の感覚がない。③前準備(並べかえ)の手間を数えずに比べる。
このページの範囲:学習指導要領解説の「アルゴリズムによる効率の違い」を、比較・計算の回数とその増え方で扱っています。O(n)・O(n²) のような記法(オーダー記法)や対数は使わず、「比例して増える」「2乗に近い増え方」「データが2倍になると1回増える(調べる範囲が半分ずつになるため)」と言葉で表しています。二分探索の一番多い回数は ⌊log₂n⌋ + 1 回です。
授業で使うとき:「5. 回数を時間に直してみる」の部品で、データの数を変えて時間の目安を見せると、手順を工夫する意味が伝わります。数値・問題はすべてこのサイトで作ったもので、プログラムの表示は実行器で、計算は検算スクリプトで確かめています。
学習指導要領:情報Ⅰ (3)ア(イ) / 参考:高等学校学習指導要領(平成30年告示)解説 情報編 情報Ⅰ (3)ア(イ)・イ(イ)(アルゴリズムによる効率の違い)、文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第3章 学習15「アルゴリズムの比較」