ソート 比較ソートアルゴリズムの最悪計算量の下界

ウィキペディア

ソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/25 09:50 UTC 版)

比較ソートアルゴリズムの最悪計算量の下界

ソートを行う際、要素間の順序の決定を2要素の大小関係の比較処理のみを用いて行うことにする。この時、$n$要素からなるリストをソートするアルゴリズムの最悪比較回数は$\Omega (n\log n)$回となる。すなわち、どんな比較ソートアルゴリズムであっても入力によっては（一般的な入力に対しては）漸近的に$n\log n$回の比較が必要となる。

この理由を説明する。ある比較ソートアルゴリズムが与えられた際、様々な入力に対する処理の手順を二分決定木として表すことができる。内部ノードは2要素の比較処理を表し、内部ノードから子ノードへの2本の枝は比較結果に応じた処理を表す。また、葉は処理の終了を表す。この時、木の高さが最悪比較回数となる。$n$要素からなるリストが入力される時、どのような二分決定木を作ったとしても、木の高さが$\Omega (n\log n)$になることを示す。二分決定木の高さを$m$とした時、木の形によらず、葉の数は$2^{m}$以下になる。$n$要素からなるリストの（添字の）置換は$n!$個存在するが、任意の入力に対してアルゴリズムが正しい出力をするためには、$n!$個の異なるリストを入力した際、それらがすべて異なる葉に到達できるようにしなければならない。よって、葉の数は$n!$以上でなければならない。以上より、$n!\leq 2^{m}$である。スターリングの公式より$\left({\frac {n}{e}}\right)^{n}<n!$なので、$\left({\frac {n}{e}}\right)^{n}<2^{m}$。よって、$m>\log _{2}\left({\frac {n}{e}}\right)^{n}=n(\log _{2}n-\log _{2}e)$。よって$m=\Omega (n\log n)$。

以上より、任意の比較ソートアルゴリズムの最悪計算量は$\Omega (n\log n)$となる。すなわち、比較ソートアルゴリズムの最悪計算量の下界は漸近的には$n\log n$となる。

マージソート、ヒープソートなどの比較ソートアルゴリズムの最悪計算量は$O(n\log n)$であるため、これらのアルゴリズムの最悪計算量は上記の下界と漸近的に一致していると言える。つまり、これらのアルゴリズムの最悪計算量は漸近的に最適である。