1.4アルゴリズムと計算量

前節でデータ構造の「入れ物」を学びました。この節では、その入れ物に対して何をどれだけ効率よく行えるか——探索と整列という2大アルゴリズムと、効率を客観的に比較する物差しであるオーダ記法を扱います。科目Bの擬似言語問題の多くはこの節の内容がベースになるため、単なる暗記ではなく各アルゴリズムがどう動くかをトレースできるレベルまで理解を深めます。

1.4.1探索アルゴリズム

• 線形探索（リニアサーチ）＝先頭から順に1件ずつ目的の値と比較していく最も単純な探索。データが整列されている必要はないが、最悪の場合は全件を調べる必要があり計算量はO(n)。
• 2分探索（バイナリサーチ）＝整列済みのデータが前提。探索範囲の中央の値と目的の値を比較し、大小関係に応じて探索範囲を半分に絞り込むことを繰り返す。計算量はO(log n)と線形探索より大幅に高速。

1.4.2整列アルゴリズム

• バブルソート＝隣り合う2要素を比較し、順序が逆なら交換する処理を繰り返す整列法。実装は単純だが、計算量はO(n^2)と大きなデータには不向き。
• クイックソート＝基準値（ピボット）を選び、それより小さい要素と大きい要素に分割し、各部分を再帰的に整列する分割統治法。平均計算量はO(n log n)と高速だが、ピボットの選び方次第で最悪O(n^2)になり得る。
• マージソート＝データを半分に分割し続けて要素1個まで分解した後、整列済みの小さな列を併合（マージ）しながら統合していく分割統治法。計算量は常にO(n log n)で安定しているが、マージ用に追加のメモリ領域が必要。

1.4.3再帰とオーダ記法

• 再帰＝手続き（関数）が自分自身を呼び出すプログラミング手法。問題を「同じ形のより小さな問題」に分解できる場合に自然に書ける（例：クイックソート・マージソート・階乗計算）。基底条件（終了条件）が必須で、これがないと無限に呼び出しが続く。
• オーダ記法（O記法）＝アルゴリズムの実行時間やメモリ使用量が、入力サイズ n の増加に対してどう増えていくかを表す記法。定数倍や低次の項を無視し、支配的な増加の傾向だけに注目する。
• 代表的なオーダの大小関係＝O(1) < O(log n) < O(n) < O(n log n) < O(n^2)。n が大きくなるほど、この順序の差は劇的に開く（例：n=1,000,000 なら O(log n) は約20だが O(n^2) は1兆）。

ある通販サイトで、100万件の商品データから特定の商品IDを検索する処理を高速化する場面を考えます。現状は線形探索で先頭から1件ずつ照合しており、最悪の場合100万回の比較が必要（O(n)）です。ここで商品IDをあらかじめ昇順に整列しておけば、2分探索が使えるようになり、比較回数は最悪でも約20回（log2(1,000,000) ≈ 20＝O(log n)）まで激減します。ただし2分探索を使うには「整列済み」という前提を維持し続ける必要があり、新規商品の追加のたびに整列を保つコストとのトレードオフを考える必要があります。次に、その整列自体をどう行うかを考えます。データ量が少なく実装のシンプルさを優先するならバブルソート（O(n^2)）でも許容範囲ですが、100万件規模では非現実的な時間がかかります。安定して高速なマージソート（常にO(n log n)）か、平均的に高速なクイックソート（平均O(n log n)、最悪O(n^2)）が現実的な選択となり、メモリ制約が厳しいならピボット選定を工夫したクイックソート、追加メモリに余裕がありワーストケースの安定性を重視するならマージソートを選ぶ、という判断になります。マージソートもクイックソートも、内部では「大きな問題を半分に分割し、小さくなった同じ形の問題を再帰的に解いて統合する」という共通の設計（分割統治法）を使っており、再帰には必ず「要素数が1以下になったらそれ以上分割しない」という基底条件が組み込まれています。このように、探索方式の選択・整列アルゴリズムの選択・再帰による実装は、すべてオーダ記法で見積もった効率を根拠に判断されます。

1.4.4この節のまとめ

• 線形探索＝O(n)（整列不要）、2分探索＝O(log n)（整列済み前提）
• バブルソート＝O(n^2)、マージソート＝常にO(n log n)、クイックソート＝平均O(n log n)・最悪O(n^2)
• オーダ記法は入力サイズ増加に対する効率の支配的な傾向を表す。再帰には基底条件が必須