3

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

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

谢谢！

4

1 回答 1

1

What would be complexity? Its all depends how do you merge N arrays of M size!

合并的复杂性：

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

对于N rowswhereeach row is sorted和containsM元素。

如果这样做（线性合并）：

  • 首先合并两行——你会得到 middle 2M size sorted array。
  • 2M array与另一个row of N sizematix合并——你会得到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)作为 total steps required is log(N)。

我想建议您学习合并排序及其复杂性。

于 2012-11-16T06:25:20.710 回答