要素どうしの比較だけを用いて n 個の要素を整列するアルゴリズムについて、最悪の場合の比較回数の下限として正しいものはどれか。

解説

正解は「$\Omega (n\log n)$」です。比較による整列は、比較結果で分岐する2分木（決定木）で表せます。n 個の要素の並べ方は n! 通りあり、どの並びも正しく整列するには決定木の葉が n! 個以上必要です。高さ h の2分木の葉は $2^h$ 個以下なので、h は ${\log }_{2}n!$ 以上となり、これは $n\log n$ のオーダーです。したがって、マージソートやヒープソートはオーダーの意味で最適です。「$\Omega (n)$」は、全要素を少なくとも1回は見るという自明な下限で、比較ソートにはより強い下限が成り立ちます。「$\Omega (n^2)$」はバブルソートなどの最悪計算量で、下限ではありません。「$\Omega (\log n)$」は小さすぎます。