行列の並べ替えの問題を考えてみましょうn x n（つまり、行と列が昇順です）。この問題の下限と上限を見つけたいと思います。
要素を並べ替えてから、最初の要素を最初の行としてO(n^2 log n)出力し、次の要素を2番目の行として出力するというようになっていることがわかりました。しかし、私はそれもであることを証明したいと思います。nnOmega(n^2 log n)
小さな例を試した後、より少ない比較を使用してこの問題を解決できれば、要素の並べ替えに必要な比較の下限にn^2 log(n/e)違反することを証明する必要があると思います。log(m!)m
それを証明する方法について何かアイデアはありますか？
http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithmsをご覧ください。
あなたの問題は、n ではなく n² 要素をソートしているように聞こえるため、たとえば、「O(n² log n²)」はマージソートに有効である可能性があります。
最初の行の最初の n 個の要素自体を並べ替える必要がない場合は、高速になる可能性がありますが、必ずしもそうとは限りません。アルゴリズムによって異なります。
最後に大事なことを言い忘れましたが、いくつかの例を試しても何かを証明することはできません。特に、統計が有効にならない小さな例(何かを示しているわけでさえありません)。