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

Question

我只是想知道合并两个大小为n和m的排序数组的时间复杂性,因为n总是大于m.

我正在考虑使用合并排序,我假设在这种情况下将消耗O(log n + m).

我不是很喜欢大哦和东西.请告诉我这个问题的时间复杂性,如果有一种解决问题的优化方法,请告诉我.

提前致谢.

Answer 1

合并两个排序列表的时间绝对不是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的前面时,这是最坏的情况.

Answer 2

注意力！此答案包含错误

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

复杂度为 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 * mO(log(n/m)) = O(log(n))