complexity-theory - 合并大小为n和m的两个排序数组的时间复杂度

Question

考虑到 n始终大于m ，我只是想知道合并大小为n和m的两个排序数组的时间复杂度是多少？

我当时在考虑使用合并排序，在这种情况下，我假设它将消耗O(log n + m)。

我对大哦和其他东西不太好。请向我建议该问题的时间复杂度，并告诉我是否有解决问题的最佳方法。

提前致谢。

Answer 1

注意!该答案包含一个错误

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

复杂度为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))，我们将得到与上述相同的渐近复杂度。