定義
O(n log n)は分割(log n)と処理(n)を掛けた時間計算量です。比較ベースソートの理論的下限です。
主な特性
- ✓分割統治アルゴリズムの計算量
- ✓効率的ソートの限界
- ✓O(n)より遅くO(n²)より速い
活用事例
こんな場面で使われます:
🔀
マージソート
分割して合わせながらソート
⚡
クイックソート
ピボット基準で分割
🏔️
ヒープソート
ヒープで最大値抽出
計算量
時間計算量
最良
O(n log n)
平均
O(n log n)
最悪
O(n log n)
空間計算量
O(n)
可視化でより深く理解する
ステップごとのアニメーションとコード実行を通じて、アルゴリズムの動作を直接確認してください。
可視化を開始