合并大小为n和m的两个排序数组的时间复杂度 [英] Time complexity for merging two sorted arrays of size n and m

问题描述

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

I was just wondering what is the time complexty of merging two sorted arrays of size n and m, given that n is always greater than m.

我当时在考虑使用合并排序，在这种情况下，我认为它将消耗O（log n + m）。

I was thinking of using merge sort, which I assume in this case will consume O(log n+m).

我对big-oh和其他东西并不满意。请给我建议这个问题的时间复杂度，并让我知道是否有解决问题的最佳方法。

I am not really good with big-oh and stuff. Please suggest me the time complexity for this problem and let me know if there is an even optimized way of solving the problem.

谢谢。

推荐答案

注意！该答案包含错误

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

A more efficient algorithm exists and it is presented in another answer.

复杂度为O（m log n）。

The complexity is O(m log n).

让长数组称为 a 并且短数组为 b ，则您描述的算法可以写为

Let the long array be called a and the short array be b then the algorithm you described can be written as

  for each x in b
      insert x into a

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

There are m iterations of the loop. Each insertion into a sorted array is an O(log n) operation. Therefore the overall complexity is O (m log n).

由于对 b 进行了排序，因此可以得出上述算法

Since b is sorted the above algorithm can be made more efficient

  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]

这可以提供更好的渐近复杂度吗？

Can this give better asymptotic complexity? Not really.

假设 b 中的元素沿 a 。然后每个插入将花费 O（log（n / m）），总体复杂度将是 O（m log（n / m））。如果存在不依赖 n 或 m的常量 k> 1 code>，这样 n> k * m 然后 O（log（n / m））= O（log（n）），我们得到与上述相同的渐近复杂度

Suppose elements from b are evenly spread along a. Then each insertion will take O(log (n/m)) and the overall complexity will be O(m log(n/m) ). If there exists a constant k>1 that does not depend on n or m such that n > k * m then O(log(n/m)) = O(log(n)) and we get the same asymptotic complexity as above.

这篇关于合并大小为n和m的两个排序数组的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！