考虑对矩阵进行排序的问题n x n（即行和列按升序排列）。我想找到这个问题的下限和上限。
我发现它O(n^2 log n)只是对元素进行排序，然后将第一个n元素输出为第一行，将下一个n元素输出为第二行，依此类推。但是我想证明它也是Omega(n^2 log n)。
在尝试了较小的示例之后，我认为我应该证明，如果我可以使用小于n^2 log(n/e)比较来解决这个问题，它将违反对元素log(m!)进行排序所需的比较下限。m
关于如何证明这一点的任何想法？
问问题
576 次
1 回答
0
看看http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms。
您的问题听起来好像您只是在对 n² 元素而不是 n 进行排序，因此 'O(n² log n²)' 可能对例如合并排序有效。
如果第一行中的前 n 个元素不必自己排序，它可能会更快，但不是必须的，这取决于算法。
最后但并非最不重要的一点是，尝试一些例子并不能证明什么，尤其是那些统计数据不起作用的小例子（它们甚至没有表明什么）
于 2014-03-13T06:20:56.160 回答