ENGINEER_GUIDANCE: 探索の最適化
実務で「計算量」を意識することは、システムのスケールアップに不可欠な素養です。データ件数 n
に対して、アルゴリズムがどれだけ「ステップ数」を要するかを確認しましょう。
1. 線形探索 (Linear Search) - O(n)
最初から最後まで一つずつチェックする最もシンプルな方法です。データが未ソート(バラバラ)な状態ではこれしか手段がありません。計算量は O(n)。小規模なリストや、一度きりの使い捨ての探索に用いられます。
2. 2分探索 (Binary Search) - O(log n)
探索範囲を毎回半分に絞り込む強力な手法です。前提条件として「データがソート済みであること」が必須です。計算量は O(log n)。100万件のデータもわずか20回程度の比較で特定できます。データベースのインデックス探索などの基礎となる考え方です。
3. ハッシュ探索 (Hash Search) - O(1)
計算によってデータの格納場所(バケット)を一意に特定する手法です。理想的な条件下ではデータ量に関わらず一瞬(計算量 O(1))で見つけ出せます。メモリを多めに使用(空間計算量)する代わりに、探索速度(時間計算量)を極限まで高める「実務で最も好まれる」最適化の一つです。