基本アルゴリズム｜コンピュータ基礎

← コンピュータ基礎一覧

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：計算量とオーダー記法・基本データ構造　|　関連：メモリ階層とキャッシュ

要点（BLUF）

探索：未整列なら線形探索 O(n)。整列済みなら二分探索 O(log n)（毎回候補を半分に絞る）。100万件でも約20回で見つかる。
整列：素朴な選択/バブルソートは O(n^2)、マージ/クイック/ヒープソートは O(n log n)。n が大きいほど差は桁違い。
トレードオフ：ソートは前処理コスト（O(n log n)）だが、その後の検索を O(n) → O(log n) に下げる。何度も検索するなら先にソートが得。

概念 ── アルゴリズムは「手順の選択」

同じ問題（探す・並べる）に複数の手順があり、計算量（計算量とオーダー記法）が違います。データ構造（基本データ構造）と手順の組み合わせで実速度が決まる。ここでは最も基本的な「探索」と「整列」を、実測の比較回数で見ます。

仕組み① ── 探索：線形 vs 二分

線形探索は先頭から順に照合。未整列でも使えるが最悪 n 回（O(n)）。

二分探索は整列済み配列の真ん中を見て、目的が左右どちらにあるか判定し、候補を毎回半分に捨てる。だから O(log n)。

flowchart TB
    s["範囲全体（n 個）"] --> m1["中央と比較 -> 半分を捨てる"]
    m1 --> s2["範囲 n/2"] --> m2["中央と比較 -> また半分"]
    m2 --> s3["範囲 n/4 -> ... -> 1"]

実測します（[[#対応ラボ]] の 06-03_search_sort.py、n=10万・末尾を探す）。

線形探索:  100,000 回  (O(n))
二分探索:       17 回  (O(log n) ≒ 17)

10万件で線形は10万回、二分はわずか17回。log2(100000) ≒ 17 の理論通り。ただし二分探索には整列済みという前提が要ります。これが次のトレードオフに繋がります。

仕組み② ── 整列：O(n^2) vs O(n log n)

選択ソート/バブルソートは、要素を二重ループで比べて並べる素朴な方法で O(n^2)。マージソートは「半分に分けて各々ソートし、併合する」分割統治で O(n log n)。クイックソートは基準値で分割し平均 O(n log n)（最悪 O(n^2) だが実用上速い）。

選択ソート(O(n^2))    :  1,999,000 回  (理論 ~ n^2/2 = 2,000,000)
マージソート(O(n log n)):     19,455 回  (理論 ~ n log n = 21,931)
比: 選択ソートはマージソートの約 103 倍の比較

n=2000 で既に約100倍の差。n が増えればこの差はさらに開きます（計算量とオーダー記法の爆発）。実測が理論オーダーとよく一致しているのが確認できます。

比較ソートの下限：要素を比較だけで並べる方式は、どんなに工夫しても O(n log n) より速くできないことが証明されています（n個の並べ方 n! を区別するのに必要な比較数の下限から）。だからマージ/クイック/ヒープは「比較ソートの理論限界に達している」優秀さ。整数など条件が付けば、比較しない基数ソート等で O(n) も可能です。

仕組み ── トレードオフ：前処理への投資

二分探索は速いが整列が前提。1回しか探さないなら、ソート（O(n log n)）するより線形探索（O(n)）の方が安い。しかし何度も探すなら、最初に1回ソートしておけば、以後の各検索が O(n) → O(log n) に下がり、トータルで得します。

flowchart LR
    once["1回だけ検索"] --> lin["線形探索 O(n)（ソート不要）"]
    many["何度も検索"] --> pre["先にソート O(n log n)"] --> bins["以後は二分探索 O(log n) ずつ"]

これは「前処理に投資して後の操作を速くする」という、計算機の至る所に現れるパターン。DBのインデックス（基本データ構造の木）、キャッシュ（メモリ階層とキャッシュ）、コンパイラの最適化（性能の評価とアムダールの法則）、すべて同じ思想です。

仕組みの直観 ── なぜこの設計か

二分探索が速い理由：1回の比較で「半分」という大量の候補を捨てられる。情報量で言えば1ビット得るたびに探索空間が半減する。だから log n。
分割統治が O(n log n) な理由：問題を半分ずつに割ると深さ log n、各深さで全体 n 個を処理。掛けて n log n。再帰で「分けて統べる」のが効く典型。
前処理に投資する理由：操作が繰り返されるなら、初期コストは回数で償却される。1回あたりのコストを下げる固定投資。償却計算量の発想。

⚠️ よくある誤解・落とし穴

「二分探索はいつでも使える」→ 整列済みが前提。未整列に使うと誤った結果。整列コストを忘れない。
「クイックソートは常に O(n log n)」→ 平均はそう。最悪（既ソート＋悪い基準選択）は O(n^2)。基準のランダム化等で回避。
「O(n log n) が整列の絶対限界」→ 比較ソートの限界。基数ソートなど比較しない方式は条件付きで O(n)。
「計算量が良ければ実装は何でも」→ 小さい n では素朴な手法が定数倍で勝つ（実用ソートは小区間で挿入ソートに切替）。局所性も効く。

対応ラボ

cs-foundations-study/labs/06-03_search_sort.py（実行して探索・整列の比較回数を確認済み）。

確認できること：線形 vs 二分、O(n^2) vs O(n log n) の実測差が理論と一致