小编use*_*833的帖子

考虑排序n x n矩阵的问题(即行和列按升序排列).我想找到这个问题的下限和上限.

我发现它O(n^2 log n)只是对元素进行排序,然后将第一个n元素输出为第一行,将下一个n元素输出为第二行,依此类推.但是我想要证明它也是Omega(n^2 log n).

在尝试较小的示例之后,我想我应该证明,如果我能够使用少于n^2 log(n/e)比较来解决这个问题,那么它将违反log(m!)排序m元素所需的比较的下限.

关于如何证明这一点的任何想法？