10

我只是想知道合并两个大小为 n 和 m 的排序数组的时间复杂度是多少，因为n 总是大于 m。

我正在考虑使用归并排序，我假设在这种情况下会消耗 O(log n+m)。

我不太擅长大哦之类的。请建议我这个问题的时间复杂度，如果有解决问题的优化方法，请告诉我。

4

3 回答 3

35

合并两个排序列表的时间绝对不是 O(m log n)。它是 O(n+m)。

代码看起来像这样：

allocate c with length n+m
i = 1
j = 1
while i < n or j < m
  if i = n
    copy rest of b into c 
    break    
  if j = m
    copy rest of a into c
    break
  if a[i] < b[j]
    copy a[i] into c
    i=i+1
    continue
  if b[j] < a[i]
    copy b[j] into c
    j=j+1
    continue

现在，如果我们没有足够的内存来分配 c，这可以修改为仍然是 O(n+m) 时间，因为大多数硬件（例如 RAM 和硬盘）都允许块操作。当我们需要将单个项目插入到数组的中间时，将块的尾部移到一个上以腾出空间是一个单一的操作。如果您使用的硬件不允许这样做，那么每次插入可能需要 O(n)，这将是 O(n+mn) 复杂度。由于我们只需要将较小数组的元素插入到较大数组中，因此当较大数组中的元素已经在正确的位置时，我们永远不需要移动较大数组的片段。因此，n 保持不变，增加了 m 位的复杂度。当所有长度为 m 的数组 b 正确地放置在长度为 n 的数组 a 前面时，这是最坏的情况。

于 2012-10-08T14:41:45.613 回答
3

只是自己经历了这个问题，Big O 不是O(m+n)，它实际上只是O(n)。

这就是伪代码中的原因：（注意：我编写此代码来处理m > n或m == n的情况）

Merging sorted arrays A and B into C.
let ints 'i' and 'j' and 'k' = 0

while(i < A.length && j < B.length){
    if(A[i] < B[j]){
        C[k] = A[i]
        i++
    } else {
        C[k] = B[j]
        j++
    }
    k++
}

// Copies rest of A into C if A.len > B.len
while(i < A.length){ 
    C[k] = A[i]
    k++
    i++
}

// Copies rest of B into C if A.len < B.len
while(j < B.length){ 
    C[k] = B[j]
    k++
    j++
}
return C

现在我们只知道长度为n的数组大于长度为m的数组。这意味着长度为m的数组中的每个元素都有可能大于长度为n的数组中的每个元素，即使n > m（例如A[2,3,4,5,6]and B[7,8,9]），我们也不知道，这没关系。第一个循环将迭代直到i或j等于它们各自数组的长度，然后只有接下来的两个 while 循环中的一个将运行，直到 A 或 B 的其余部分添加到 C。

所以可以看出你是如何结束的O(m+n)，但是，Big O 通常处理最坏情况的运行时，因此我们知道我们将迭代长度为n的数组的次数比m多，而不管数组中元素的构成如何，所以m总是小于n。所以我们去掉m来得到O(n)。

这是因为n可以等于infinity，因此，既然这是一种可能性，那么我们知道m永远不可能是infinity，并且根据定义必须小于 infinity，因此进一步定义具有小于 n 的常数值（因为它在某个点停止增长到无穷大，因为只有n可以是无限的）。由于我们在确定 Big O 运行时时删除了常量，所以我们得到O(n).

显然我迟到了几年，哈哈，但我希望这能为将来可能遇到这种情况的其他人扫清空气:)

于 2020-08-31T00:08:56.577 回答
-13

注意力！此答案包含错误

存在更有效的算法，并在另一个答案中提出。

复杂度为 O(m log n)。

让长数组被称为a短数组，b那么你描述的算法可以写成

  for each x in b
      insert x into a

循环有 m 次迭代。每次插入排序数组都是 O(log n) 操作。因此总体复杂度为 O (m log n)。

由于b已排序，上述算法可以更高效

  for q from 1 to m
      if q == 1 then insert b[q] into a
      else 
         insert b[q] into a starting from the position of b[q-1]

这可以提供更好的渐近复杂度吗？并不真地。

假设 中的元素b沿 均匀分布a。然后每次插入都会进行O(log (n/m))，整体复杂性将是O(m log(n/m) ). 如果存在一个k>1不依赖于n或m这样的常数，n > k * m那么O(log(n/m)) = O(log(n))我们得到与上面相同的渐近复杂度。

于 2012-06-14T18:48:14.147 回答