プログラミング応用 — アルゴリズムと計算量

同じ問題を解くプログラムでも、アルゴリズムの選び方によって、一瞬で終わるものと何年かかっても終わらないものがあります。データが大規模になった現代、「動くプログラム」と「使えるプログラム」の差を分けるのが計算量の考え方です。この講義では、O記法による計算量の表し方と、探索・整列の代表的アルゴリズムの効率を学びます。

計算量とO記法

アルゴリズムの効率は、「データの個数 n が増えたとき、処理の手間がどんな勢いで増えるか」で評価します。これを表す記法がO記法（オーダー記法）です。細かい係数は無視し、増え方の「形」だけに注目します。

・O(1)：nに関係なく一定。例: 配列のi番目を直接取り出す。
・O(log n)：nが倍になっても手間は1回増えるだけ。例: 二分探索。
・O(n)：nに比例。例: 線形探索、合計の計算。
・O(n log n)：高速な整列の水準。例: マージソート、クイックソート（平均）。
・O(n²)：nの2乗に比例。nが10倍になると手間は100倍。例: バブルソート、選択ソート。

探索 — O(n) と O(log n) の差

線形探索は先頭から順に調べる方法で、最悪 n 回の比較が必要です（O(n)）。二分探索は整列済みデータの真ん中と比較して範囲を半分ずつに絞る方法で、最悪でも「nを1になるまで2で割れる回数」＝約 log₂ n 回で済みます（O(log n)）。

整列（ソート）のアルゴリズム

バブルソートは、隣り合う2つを比較して順序が逆なら交換する操作を繰り返す、最も単純な整列法です。n個のデータでは、1巡目にn−1回、2巡目にn−2回…と比較するので、比較回数は合計 n(n−1)÷2 回、つまりO(n²)です。n＝10なら 10×9÷2＝45回ですが、n＝10,000なら約5,000万回に跳ね上がります。選択ソート（残りの中から最小値を選んで先頭に置いていく）も同じくO(n²)です。

これに対し、データを半分ずつに分けて整列し併合するマージソートや、基準値より小さい組と大きい組に振り分けていくクイックソートはO(n log n)で動きます。n＝100万のとき、n²は1兆（10¹²）ですが、n log₂ n は約2,000万（10⁶×20＝2×10⁷）。約5万倍の差であり、実用の整列にはO(n log n)のアルゴリズムが使われます。

アルゴリズム設計の工夫

効率のよいプログラムを書く発想として、①分割統治法（問題を小さく分けて解き、結果を組み合わせる。マージソートや二分探索の考え方）、②一度計算した結果を記録して再利用する（同じ計算の繰り返しを避ける）、③適切なデータ構造を選ぶ（探す回数が多いなら整列やインデックスを先に作っておく）などがあります。データベースの「インデックス」も、検索をO(n)からO(log n)級に高速化する仕組みであり、この講座で学んだ内容はすべてつながっています。

練習問題

1. 次の計算量を処理が速い（増え方が緩やかな）順に並べなさい。 O(n²)、O(1)、O(n)、O(log n)
2. 整列済みの10,000件のデータから二分探索で値を探すとき、比較は最大何回必要か。2¹³＝8,192、2¹⁴＝16,384 を使って答えなさい。
3. バブルソートで100個のデータを整列するときの比較回数を求めなさい。また、データ数が10倍の1,000個になると比較回数はおよそ何倍になるか答えなさい。