我们有一个 n x m 矩阵,其行已排序,我们需要按升序打印矩阵中的数字。列没有必要排序。我想到的解决方案是简单地合并矩阵中的行,将它们视为单独的列表(基本上是合并排序中的合并步骤),在合并排序中需要 O(n)。我想知道在这种情况下合并 n 个单独的数组的复杂性是多少。我以为会是 O(n x m) 但我不确定。
另外,按升序打印数字的更好方法是什么?一次合并 n 个列表还是一次合并 2 个列表直到我们考虑所有行?
谢谢!
最佳答案
What would be complexity? Its all depends how do you merge N arrays of M size!
合并复杂度:
M
大小数组按顺序进行。所以这一步的复杂度是O(2M)。 For
N rows
whereeach row is sorted
and containsM
elements.
如果这样做(线性合并):
2M size sorted array
. 2M array
与另一个 row of N size
matix--你会得到3M size sorted array
. 以这种方式合并
takes N steps
和 complexity would be O(N*M)
.更好的方法(分而治之):
merge all N/2 pairs first and merge them
.例如对行(1,2);行(3,4); row(5,6) ......你会得到
= N/2 pairs each of 2M size
. make pair of two merged arrays each of size 2M from previous step
然后合并它们——你会get N/4 sorted array of 4M size
.((2M 与其他 2M 阵列的合并 -> 4M 并且复杂度为 O(2M + 2M) = O(4M)) 逐步合并所有这些中间件
sorted arrays util you gets a single sorted array of size N*M
.而这个时间复杂度将是 M*N*log(N) 总计 steps required is log(N)
.我想推荐你学习merge-sort and its complexity.
关于sorting - 从行已排序的 n x m 数组中按升序打印数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13410763/