考虑对 n x n 排序的问题矩阵(即行和列按升序排列)。我想找到这个问题的下限和上限。
我发现它是O(n^2 log n)只需对元素进行排序，然后输出第一个 n元素作为第一行，下一个 n元素作为第二行，依此类推。
但是我想证明它也是Omega(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 个元素不必自己排序，它可能会更快，但不是必需的，这取决于算法。
最后但并非最不重要的一点是，尝试一些例子并不能证明某些事情，尤其是那些统计数据不起作用的小例子(它们甚至没有表明什么)
关于sorting - 如何找到矩阵排序的下界？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14777653/