如何找到矩陣排序的下界？

Question

考慮排序n x n矩陣的問題（即行和列按升序排列）。我想找到這個問題的下限和上限。

我發現它是O(n^2 log n)只需排序元素，然後輸出第一行的第一個元素n，第二行的下一個n元素，依此類推。不過我想證明它也是Omega(n^2 log n)。

嘗試小例子之後，我覺得我應該證明，如果我能解決使用少於n^2 log(n/e)比較這個問題，那就違反了log(m!)下界到m元素進行排序需要比較。

關於如何證明這一點的任何想法？

Answer 1

看看http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms。

你的問題聽起來像你只是排序n²元素而不是n，因此'O（n²log n2）'可能對mergesort有效。

如果第一行中的前n個元素不必自己排序，它可能會更快，但並不是必須的，它取決於算法。

最後但並非最不重要的是，嘗試一些例子是沒有辦法證明的東西，尤其是小統計數據不會生效的小問題，（他們甚至沒有指出什麼）