情報の勉強高校 情報Ⅰ

第3章 コンピュータとプログラミング

アルゴリズムの比較(効率)

同じ問題を解く手順(アルゴリズム)がいくつもあるとき、どれがよいかを比べる考え方を学びます。比較や計算の回数で比べること、データが増えたときの回数の増え方(計算量の考え方)が分かります。

説明

1. 同じ問題でも、手順はいくつもある

「1 から 100 までの合計」を求めるとき、1つずつ足していけば足し算が100回要ります。でも、端から組にすると、1 + 100、2 + 99、… とどの組も 101 になり、それが50組あるので、式1つで計算できます。

答えは同じ 5050 でも、手間はまったく違います。同じ問題を解くアルゴリズムはいくつもあり、手間(効率)が違うのです。

方法A:1つずつ足していく0 + 1 + 2 + 3 + … + 100足し算 100 回= 5050方法B:式で一度に計算する(1 + 100) × 100 ÷ 2計算 3 回= 50501239899100…端から組にすると、どの組も 101101 が 50 組 → 101 × 50 = 5050
  1. (01)goukei = 0
  2. (02)i を 1 から 100 まで 1 ずつ増やしながら繰り返す:
  3. (03) goukei = goukei + i
  4. (04)表示する(goukei, " ", (1 + 100) * 100 ÷ 2)

表示:5050 5050

2. 時間ではなく「回数」で比べる

かかった時間で比べると、速いコンピュータを使っただけで結果が変わってしまいます。そこで、比較や計算などの基本の操作を何回するかで比べます。回数ならコンピュータに関係なく同じです。

回数は、データの並び方で変わることがあります。8個のデータの線形探索せんけいたんさくなら、探す値が先頭にあれば1回、最後なら8回です。どんな場合でも間に合うように、普通は一番多いときで比べます。

線形探索(8個)で、ある値を探すときの比較回数一番少ない1 回先頭にあった平均4.5 回どこにあるかが同じ割合なら一番多い8 回最後にあった・なかった効率を比べるときは、普通「一番多いとき」(どんな場合でもこの回数以内に終わる)

3. データが増えると、回数はどう増える?

カードが5枚なら、どんな方法で並べても大差ありません。でも1万枚、100万枚になると、方法によって手間がまったく違ってきます。

下のグラフは、データの数 n が増えたときの回数です。式で計算する方法はずっと同じ回数、二分探索にぶんたんさくはほとんど増えません。線形探索たんさくは n に比例してまっすぐ増え、選択ソートなどの並べかえ(n(n−1)/2)は、n が大きくなるほど急に増えます。

データの数 n と、一番多いときの回数05010015020005101520データの数 n →回数並べかえn(n−1)/2線形探索 n下の方を拡大(0〜20回)1020線形二分式
机に向かう高校生が、手元の数枚のカードと、天井近くまで積み上がったカードの山を見比べておどろいている絵
数枚と山ほどでは、同じ手順でも手間がまったく違う。

4. データを2倍にすると

増え方の違いは、データを2倍にしてみるとよく分かります。線形探索は2倍、選択ソートの比較は約4倍(2 × 2)、二分探索は1回増えるだけです。

データの数に対して回数がどう増えるかを、計算量(けいさんりょう)と呼びます。「比例して増える」「2乗に近い増え方をする」のように言い表します。

データを 1,000個 → 2,000個 にすると1,000個2,000個増え方式で計算33変わらない二分探索10111回増える線形探索1,0002,0002倍選択ソート499,5001,999,000約4倍回数の「増え方」がアルゴリズムの効率を決める

比べるのは回数そのものより「データが増えたときの増え方」。

5. 回数を時間に直してみる

1秒間に100万回比べられるコンピュータで、データの数を変えてみましょう。100万個を選択ソートで並べると、比較だけで約5.8日かかります。線形探索は1秒、二分探索は一瞬です。

コンピュータが速くなっても、増え方の大きいアルゴリズムは、データが増えるとすぐに追いつかなくなります。だから、手順の工夫が大切なのです。

比較の回数だけを数えた目安です(実際には、代入などほかの操作の時間もかかります)。

6. どれがよいかは場合による

回数が少ないアルゴリズムが、いつも一番よいとは限りません。二分探索は、先に並べかえておく手間がかかります。1回だけ探すなら、並べかえずに線形探索をした方が手間は少なくなります。

並べかえでも、クイックソートは普通とても速いのですが、並び方によっては遅くなることがあります。データの数・並び方・何回使うかを考えて選びます。

1回だけ探す/データが並んでいない→ 線形探索でよい並べかえる手間の方が大きい何回も探す/データが多い→ 一度並べかえて二分探索並べかえは1回で、あとは速いデータが少ない(数十個)→ どれでも差は小さい分かりやすい方法でよい

7. プログラムから回数を数える

共通テストでは、プログラムのある行が何回実行されるかを考える問題が出ることがあります。二重の繰り返しでは、外側の1回ごとに内側が何回まわるかを書き出して足します。

下のプログラムは、i が 0 のとき内側が5回、1 のとき4回、… とまわります。合計 5 + 4 + 3 + 2 + 1 = 15 回で、6個のデータの選択ソートの比較の回数と同じです。

ひとことで言うと回数で比べ、データが増えたときの回数の増え方で効率を見る。

例題

例題1 探索の回数を比べる

小さい順に並んだ 64個のデータから値を探します。線形探索と二分探索で、比較の回数は一番多くてそれぞれ何回ですか。データが 128個になったらどうですか。

例題2 二重の繰り返しの回数

次のプログラムで表示される数はいくつですか。また、1行目を n = 10 にすると、表示される数は何倍になりますか。

  1. (01)n = 5
  2. (02)kaisu = 0
  3. (03)i を 1 から n まで 1 ずつ増やしながら繰り返す:
  4. (04) j を 1 から n まで 1 ずつ増やしながら繰り返す:
  5. (05) kaisu = kaisu + 1
  6. (06)表示する(kaisu)

練習

1
アルゴリズムの効率を比べるとき、普通何を元に比べますか。
2
線形探索で、データの数が2倍になると、比較の回数(一番多いとき)はどうなりますか。
3
小さい順に並んだ1000個のデータを二分探索すると、比較は一番多くて10回です。データが 2000個になると、一番多くて何回ですか。
4
選択ソートで 20個のデータを並べるとき、比較の回数は全部で何回ですか(10個のときは45回です)。
5
並んでいない1000個のデータから、ある値を1回だけ探します。正しくさがせる方法のうち、比較の回数が最も少なくてすむのはどれですか。

さわってみよう

並べかえ:並び方で回数は変わる?

同じ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)
問1
このプログラムを実行したとき、表示される kaisu の値を答えよ。
問2
回答が100件のとき、方法Aで kaisu はいくつになるか。最も適当なものを選べ。
問3
回答が100件から1000件に増えると、方法Aの kaisu はおよそ何倍になるか。最も適当なものを選べ。
問4
方法Bについて述べた文として、最も適当なものを選べ。

この単元が出た過去問の解説

ちょっと寄り道:豆知識・こぼれ話

試験に出るとはかぎりませんが、知っていると情報がもっと面白くなる話です。

都市が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倍で1回増える)の感覚がない。③前準備(並べかえ)の手間を数えずに比べる。

このページの範囲:学習指導要領解説の「アルゴリズムによる効率の違い」を、比較・計算の回数とその増え方で扱っています。O(n)・O(n²) のような記法(オーダー記法)や対数は使わず、「比例して増える」「2乗に近い増え方」「データが2倍になると1回増える(調べる範囲が半分ずつになるため)」と言葉で表しています。二分探索の一番多い回数は ⌊log₂n⌋ + 1 回です。

授業で使うとき:「5. 回数を時間に直してみる」の部品で、データの数を変えて時間の目安を見せると、手順を工夫する意味が伝わります。数値・問題はすべてこのサイトで作ったもので、プログラムの表示は実行器で、計算は検算スクリプトで確かめています。

学習指導要領:情報Ⅰ (3)ア(イ) / 参考:高等学校学習指導要領(平成30年告示)解説 情報編 情報Ⅰ (3)ア(イ)・イ(イ)(アルゴリズムによる効率の違い)、文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第3章 学習15「アルゴリズムの比較」