use*_*833 5 sorting matrix asymptotic-complexity lower-bound
考虑排序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你的问题听起来像是你只是对 n\xc2\xb2 元素而不是 n 进行排序，因此 \'O(n\xc2\xb2 log n\xc2\xb2)\' 可能对于例如合并排序有效。
\n\n如果第一行中的前 n 个元素不必自行排序，它可能会更快，但不一定，这取决于算法。
\n\n最后但并非最不重要的一点是，尝试一些例子并不能证明什么，尤其是统计数据不起作用的小例子（它们甚至没有表明什么）
\n| 归档时间： |
|
| 查看次数： |
454 次 |
| 最近记录： |