sorting - 从行已排序的 n x m 数组中按升序打印数字

Question

我们有一个 n x m 矩阵，其行已排序，我们需要按升序打印矩阵中的数字。列没有必要排序。我想到的解决方案是简单地合并矩阵中的行，将它们视为单独的列表(基本上是合并排序中的合并步骤)，在合并排序中需要 O(n)。我想知道在这种情况下合并 n 个单独的数组的复杂性是多少。我以为会是 O(n x m) 但我不确定。

另外，按升序打印数字的更好方法是什么？一次合并 n 个列表还是一次合并 2 个列表直到我们考虑所有行？

谢谢!

Answer 1

What would be complexity? Its all depends how do you merge N arrays of M size!
合并复杂度:

合并两个已排序 M大小数组按顺序进行。所以这一步的复杂度是O(2M)。

For N rows where each row is sorted and contains Melements.

如果这样做(线性合并):

先合并两行——你会得到中间 2M size sorted array .

合并 2M array与另一个 row of N size matix--你会得到3M size sorted array .

以这种方式合并 takes N steps和 complexity would be O(N*M) .

更好的方法(分而治之):

首先合并所有两对连续行 (1,2), (3,4) 这给你 N/2 对 2M 大小。在下一步合并成对。如下所述。

首先制作一对两排和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.