比較ソートアルゴリズムの時間計算量の下限
定理
比較ソートアルゴリズムの時間複雑度は、せいぜい$\Omega ( n \log n )$である。
説明
アルゴリズムは元から不思議なものだけど、挿入ソートのような効率的なアルゴリズムでさえクイックソートに負けてしまうことから、もっと効率的なアルゴリズムが存在しないかと思ってしまうのは当然だ。幸か不幸か、この証明によって、それより効率的なアルゴリズムを考える必要はない。
もちろん、一般的な比較アルゴリズムではなく、特別な条件が与えられた場合には、これよりも速いアルゴリズムも存在する。
証明
大きさが$n$のデータが与えられたとしよう。データが並べられるすべての場合の数は、順列で計算した時$n!$になる。この中で正しくソートされた場合は一つだが、$n$個のデータの中から二つを比較するたびに、それと異なる残りの場合の半分を除外できる。次の例で理解しよう。
例えば、データ$x_{1}$、$x_{2}$、$x_{3}$が与えられている場合、可能な場合の数は$3! = 6$で、次のように6つの場合がある。 $$ ( x_{1} , x_{2} , x_{3} ) \\ ( x_{1} , x_{3} , x_{2} ) \\ ( x_{2} , x_{1} , x_{3} ) \\ ( x_{2} , x_{3} , x_{1} ) \\ ( x_{3} , x_{1} , x_{2} ) \\ ( x_{3} , x_{2} , x_{1} ) $$ 上記の説明により、$x_{2} < x_{1}$であることを確認すると、これに反する半分の場合は除外され、次の三つの場合だけが残る。 $$ ( x_{2} , x_{1} , x_{3} ) \\ ( x_{2} , x_{3} , x_{1} ) \\ ( x_{3} , x_{2} , x_{1} ) $$ もし$x_{1} < x_{3}$ならば、比較ソートアルゴリズムは$( x_{2} , x_{1} , x_{3} )$を返して終わりで、$x_{3} < x_{1}$ならば最後に$x_{2}$と$x_{3}$を比較して正しくソートされた場合を返さなければならない。
このように、比較によって場合の数を半分ずつ減らしていくが、ソートを完了させるには不十分な情報が残っている場合、最悪の場合には$\left \lceil \log_{2} n! \right \rceil \approx \log n!$回の計算を行う必要がある。
スターリングの近似: $$ \lim_{n \to \infty} {{n!} \over {e^{n \ln n - n} \sqrt{ 2 \pi n} }} = 1 $$
スターリングの近似によると、$\displaystyle n! \approx e^{n \log n - n } \sqrt{ 2 \pi n }$であるため、 $$ \begin{align*} \log n! =& \log e^{n \log n - n } \sqrt{ 2 \pi n } \\ =& n \log n - n + \log \sqrt{ 2 \pi n } \\ =& n \log n - n + {{1} \over {2}} \log n + {{1} \over {2}} \log 2 \pi \\ =& \Omega ( n \log n ) \end{align*} $$
■