対数時間 O(log n) — 分割統治の力
バイナリサーチなどのO(log n)対数アルゴリズムが、各ステップで問題を半分にして効率を達成する仕組みを学びます。比較表と実例付き。
Complexity Classes
詳細な説明
O(log n)対数時間とは？
アルゴリズムがO(log n)時間で実行されるのは、各ステップで問題サイズを定数倍縮小（通常は半分）する場合です。
log nの成長速度
| n | log₂ n |
|---|---|
| 10 | 3.3 |
| 100 | 6.6 |
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
10億要素でも約30ステップしか必要ありません。
代表的なO(log n)アルゴリズム
- バイナリサーチ — ソート済み配列で中央要素をチェックし、半分を破棄
- 平衡BST操作 — AVL木や赤黒木での検索、挿入、削除
- 繰り返し二乗法 —
x^nをO(log n)回の乗算で計算 - バイナリリフティング — 木の祖先をO(log n)で検索
前提条件
ほとんどのO(log n)検索アルゴリズムは、ソート済みまたは構造化された入力を必要とします。
ユースケース
データベースインデックス（B-tree）、ソート済みデータセットでのバイナリサーチ、静的または半静的データに対する多数のクエリに効率的に応答する必要があるシナリオで重要です。