アルゴリズムの効率｜高校情報Ⅰ

0. どういうまとまりか

同じ結果を出すアルゴリズムでも、データが増えたときの処理の回数の増え方が違います。
データが少ないうちは差が見えなくても、多くなると何百倍・何万倍もの差になります。

処理の回数の増え方	例	データが 2 倍になると	データが 10 倍になると
$lo g_{2} n$ に比例	二分探索	1 回増える	3〜4 回増える
n に比例	線形探索	2 倍	10 倍
$n lo g_{2} n$ に比例	クイックソート（平均）	2 倍より少し多い	10 倍より少し多い
n の 2 乗に比例	選択ソート・バブルソート・挿入ソート	4 倍	100 倍

分かれ目は次の 3 つ。

効率は、実際の秒数ではなく、データ数 n が増えたときの処理の回数の増え方で比べる。
n の 2 乗に比例するものは、データが 2 倍で 4 倍、10 倍で 100 倍になる。
データが多くなるほど差は開くので、量の多いデータでは効率のよいアルゴリズムを選ぶ工夫が要る。

1. 計算量の考え方

根拠: 学習指導要領情報Ⅰ-(3)-ア-(イ)

処理にかかる時間はコンピュータの速さで変わるので、アルゴリズムそのものの良し悪しは
データの数 n に対して、比較や代入を何回行うかで比べます。これを計算量（時間計算量）といいます。

アルゴリズムの計算量（時間計算量）とは何か？

データの数が増えたとき、処理の回数（手間）がどのように増えるかを表したもの

アルゴリズムの効率を比べる目安。細かな回数より「n に比例」「n の 2 乗に比例」といった増え方を見る。

アルゴリズムの効率を、実際にかかった秒数ではなく処理の回数で比べるのはなぜか？

秒数はコンピュータの性能によって変わるが、処理の回数はアルゴリズムだけで決まるから

同じプログラムでも、速いコンピュータで動かせば秒数は短くなる。

計算量を表す O(n)（オーダー n）という書き方は、何を意味するか？

処理の回数が、データの数 n におおよそ比例して増える

O(n²) なら n の 2 乗に比例、O(log n) なら n の対数に比例。係数や小さい項は無視して増え方だけを表す。

2. 増え方の比べ方

根拠: 学習指導要領情報Ⅰ-(3)-ア-(イ)

増え方の違いは、データを 2 倍・10 倍にしたとき処理の回数が何倍になるかで見るとつかみやすくなります。

処理の回数が n の 2 乗に比例するアルゴリズムで、データを 10 倍にすると、処理の回数はおよそ何倍になるか？

およそ 100 倍

10 の 2 乗。データが 2 倍なら 4 倍。

処理の回数が n に比例するアルゴリズムで、データを 10 倍にすると、処理の回数はおよそ何倍になるか？

およそ 10 倍

線形探索がこの例。

処理の回数が $lo g_{2} n$ に比例するアルゴリズムで、データを 8 倍にすると、処理の回数はどう変わるか？

3 回ぶん増えるだけ

8 は 2 の 3 乗なので、半分にする回数が 3 回増える。二分探索がこの例。

線形探索と二分探索の計算量を、O の記法で表すと？

線形探索は O(n)、二分探索は O(log n)

データが多いほど二分探索が有利。ただし二分探索は整列済みであることが前提。

選択ソート・バブルソートと、クイックソート（平均）の計算量を、O の記法で表すと？

選択ソート・バブルソートは O(n²)、クイックソートは平均 O(n log n)

データが多いほど、クイックソートのほうが大幅に速い。

3. 性能を改善する工夫

根拠: 学習指導要領情報Ⅰ-(3)-ア-(イ)

プログラムが正しく動いても、データが増えると実用にならないほど遅くなることがあります。
アルゴリズムやデータ構造を見直して、同じ結果をより少ない手間で得るのが性能の改善です。

データが少ないうちは差が無かった 2 つのプログラムで、データを増やすと処理時間が大きく違ってくるのはなぜか？

処理の回数の増え方（計算量）が違い、その差がデータが多くなるほど大きく開くから

n に比例するものと n の 2 乗に比例するものは、n が 10 なら 10 倍の差でも、n が 1 万なら 1 万倍の差になる。

同じ結果を出すプログラムの処理時間を短くするには、まず何を見直すのが効果的か？

アルゴリズム（とデータ構造）を、計算量の小さいものに変える

コンピュータを速くしても数倍にしかならないが、計算量の小さいアルゴリズムに変えると、データが多いとき何百倍も速くなることがある。

何度も値を探すデータで、先に整列しておく手間をかけてもよいのはなぜか？

整列は一度で済み、その後の探索を二分探索で速くできるから

探す回数が多いほど、整列の手間を取り返せる。探すのが 1 回だけなら線形探索のほうが手間が少ない。

練習問題

問 1　選択ソートの比較の回数は、データが n 個のとき $\frac{n ( n - 1 )}{2}$ 回である。
データが 1000 個から 2000 個に増えると、比較の回数は何回から何回になり、およそ何倍になるか。

499500 回から 1999000 回になり、およそ 4 倍

1000 × 999 ÷ 2 = 499500、2000 × 1999 ÷ 2 = 1999000。
n の 2 乗に比例するので、データが 2 倍なら回数はおよそ 2 の 2 乗の 4 倍になる。

問 2　次のプログラムで、n が 8 のときと 1024 のときに表示される値を答えよ。

n = 8
count = 0
i = n
while i > 1:
    i = i // 2
    count = count + 1
print(count)

8 のとき 3、1024 のとき 10

i は 8, 4, 2, 1 と半分になり、1 になるまでに 3 回まわる。1024 は 2 を 10 回かけた数なので 10 回。
半分にし続ける処理の回数は $lo g_{2} n$ で、データが 128 倍になっても回数は 7 回増えるだけ。二分探索が速い理由と同じ。