線形対数時間 O(n log n) — 最適ソートの境界
比較ベースのソートの理論的下界であるO(n log n)線形対数計算量を探求します。マージソート、クイックソート、ヒープソート、比較モデルの証明をカバー。
Complexity Classes
詳細な説明
O(n log n)線形対数時間とは？
**O(n log n)**は、アルゴリズムが約n × log₂(n)回の操作を行うことを意味します。線形よりはやや遅いですが、二次よりは劇的に高速です。
O(n log n)ソートアルゴリズム
| アルゴリズム | 最悪 | 平均 | 空間 | 安定? |
|---|---|---|---|---|
| マージソート | O(n log n) | O(n log n) | O(n) | Yes |
| クイックソート | O(n²) | O(n log n) | O(log n) | No |
| ヒープソート | O(n log n) | O(n log n) | O(1) | No |
| Tim sort | O(n log n) | O(n log n) | O(n) | Yes |
実用的な影響
n = 1,000,000の場合:
- O(n log n) ≈ 20,000,000操作
- O(n²) = 1,000,000,000,000操作
50,000倍の差 — 適切なソートアルゴリズムの選択が非常に重要な理由です。
ユースケース
大規模データセットのソート、検索インデックスの構築、凸包の計算、マージコストが線形な分割統治処理の目標計算量です。