読者です 読者をやめる 読者になる 読者になる

オタクof数理の共同ブログ

京大情報学科数理工学コースの学生4人による共同ブログです

O(nlogn)より速いソートが存在しないこと

zalgo 数学

こんにちは。zalgo(@zalgo3)です。

クイックソートとかヒープソートO(n\log n)で行えることは有名ですね。
実はソートについては次の定理が成り立ちます。

定理
長さnの列のソートの計算量の下界は\Omega (n\log n)である。

証明
ソートは、2つの要素を比較し、列を並び替える操作を繰り返すことにより行われる。
この流れを二分木で表す(比較の結果に応じて分岐していく)。
すると、葉が最終的な列を表している。
任意のソートが行えるためには、葉の数はn!個必要である。
\therefore二分木の高さをhとすると、
\displaystyle h\geq \log_2 n!
h=\Omega (n\log n)であることを示せば良い。
Landauの記号の定義から、nは十分大きいとみなしてよい。
Stirlingの公式
n!\simeq \sqrt{2\pi n}\left( \frac{n}{\mathrm{e}}\right)^n
より、
\log_2 n!=\Omega (n\log n)

有名な証明なので知ってても損はないと思います!