マトリックスソートの下限はどのようにして見つけることができますか？

Question

n x n行列のソートの問題を考えてください（つまり、行と列は昇順です）。私はこの問題の下限と上限を見つけたいと思っています。

私はそれだけの要素をソートし、次にように最初の行として第n要素、第二行として次n要素とを出力しO(n^2 log n)であることを見出しました。 しかし、私もそれがOmega(n^2 log n)であることを証明したいと思います。

小さい例を試した後、私は私が未満n^2 log(n/e)比較を使用してこの問題を解決することができれば、それはmの要素をソートするために必要な比較のために、下限log(m!)に違反することを証明するべきだと思います。

これを証明する方法はありますか？

Answer 1

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithmsをご覧ください。

問題は、nの代わりにn²要素をソートするようなものなので、例えば、「O（n²logn²）」はmergesortに対して有効です。

最初の行の最初のn個の要素をソートする必要がない場合は、高速である必要がありますが、必要ではなく、アルゴリズムに依存します。

最後に、いくつかの例を試してみることはありません。統計的に効果がない小さなもの（特に何も示していないもの）