計算量と二分探索

1. アルゴリズムの効率の指標：計算量

アルゴリズムの効率を測るとき、「手元のPCで実行したら 0.5秒だった」という測定の仕方は不適切です。なぜなら、PCの性能（CPUやメモリの速度）やプログラミング言語の種類によって実行時間は変わってしまうからです。

そこで、コンピュータサイエンスでは「処理するデータ数Nが増えたとき、計算ステップ数がどの程度の割合で増加するか」という数学的な評価基準を使います。これが計算量（Computational Complexity）です。

計算量の表記には、O記法（Big-O Notation）を使います。

2. 線形探索（Linear Search）：O(N)

あるデータ群（例えば配列）の中から、目的の値を見つけ出す最も素朴な方法が線形探索（Linear Search）です。

これは、配列の「先頭の要素から末尾に向かって、順番に1つずつ目的の値と一致するかチェックする」という方法です。

最悪の場合、目的のデータが末尾にあるか存在しないため、N回の比較が必要です。よって最悪計算量は O(N) です。

3. 二分探索（Binary Search）：O(log N)

検索対象のデータが事前にソート（並び替え）されている場合、高速な二分探索（Binary Search）を使えます。

二分探索の考え方は、辞書で単語を引くときや、数当てゲーム（1〜100の中で数字を当てるゲーム）と全く同じです。

1. まず、並んでいるデータ群の「ちょうど真ん中の値」を確認します。
2. 探したいターゲットの値が、その真ん中の値よりも「大きい」か「小さい」かを判定します。
3. もしターゲットの方が大きければ、真ん中より「左側半分」には絶対にデータはないことが確定するため、探索範囲を「右側半分」に絞り込みます（小さければその逆）。
4. 絞り込まれた新しい範囲に対して、再びステップ1（真ん中を確認）を繰り返します。

この手法は要素数が大きくなるほど効果的です。探索範囲が毎ステップで半分に縮小していくため、高速に処理できます。

データ数Nに対する最悪計算回数は、数学的に $\log_2 N$ 回になります。よって、最悪計算量は O(log N) です。

4. O(N) と O(log N) の速度差

データ数が少ないときは、線形探索 O(N) も二分探索 O(log N) も実行時間に大きな差はありません。 しかし、データ数が大きくなると、この2つの実行時間には大きな差が生じます。

例えば、日本の全人口（約1億2000万人）の名簿から特定の名前を検索する場合を考えてみます。

• 線形探索 O(N) の場合：
  最悪で 1億2000万回 の比較ループを実行します。スマホやPCでも、データ読み込みとループ処理で数秒〜数十秒の待ち時間が発生します。
• 二分探索 O(log N) の場合：
  最悪でもわずか 27回（$\log_2 120,000,000 \approx 26.8$）の比較だけで完了します。27回といえば、CPUからすれば一瞬（数ナノ秒）であり、人間には完全にリアルタイム（0秒）で表示されます。

データ数が大幅に増えても計算回数は数十回しか増えません。この特徴により、大規模な検索エンジンなどのシステムにおいて高速な検索処理が可能になります。

次のセクションでは、直線的な並びではなく、データの親子関係などを網の目のように表現する非線形データ構造「木構造」と「グラフ」について学びます。