1/8
Loading...
🌳O(n log n)とは？
ツリー構造で「なぜn × log n」か見ましょう! 📊 ポイント: • レベル数 = log₂(n) = 半分に分ける回数 • 各レベルでn個の要素を処理 このツリーを見てください: 各レベル右側に「= 8個」がありますね？ 毎レベルで合計n個を処理します!
Loading...
ツリー構造で「なぜn × log n」か見ましょう! 📊 ポイント: • レベル数 = log₂(n) = 半分に分ける回数 • 各レベルでn個の要素を処理 このツリーを見てください: 各レベル右側に「= 8個」がありますね？ 毎レベルで合計n個を処理します!
O(n log n)は分割(log n)と処理(n)を掛けた時間計算量です。比較ベースソートの理論的下限です。