分而治之k-way-merge算法的时间和space复杂度

Question

假设A是k个数组的数组。每个内部数组都已排序并包含 m 个元素。

鉴于此算法用于合并 A 中的 K 排序数组：

// A is array of sorted arrays  
K-arrays-merge(A)   
1.  if A.length == 1
2.      return first element of A
3.  half = length[A] / 2
4.  firstHalfArray = new array[half][m];
5.  secondHalfArray = new array[half][m];
6.  for (i = 0; i < half; i++)
7.      do firstHalfArray[i] = A[i];
8.  for (i = half; i < length[A]; i++)
9.      do secondHalfArray[i] = A[i];
10. secondHalfArray = Copy second half arrays from A
11. a = K-arrays-merge(firstHalfArray)
12. b = K-arrays-merge(secondHalfArray)
13. return merge(a,b) // This is a merge between two sorted arrays with time complexity of O(n)

为什么这个算法的时间复杂度是O(m*klogk)?

我的第一个想法是递归方法运行 logk 次，在每一轮中复制数组是 O(m * k) 并且合并排序是 O(mi log (mi)) 其中 1 <= i <= logk

查看分而治之步骤时：

除 - 计算中间点是 O(1)，复制数组是 O(mk)
征服 - 2T(k/2) - 递归调用。
合并 - 复杂度为 O(mi log (mi)) 的合并排序，其中 1 <= i <= logk.

我不知道如何计算时间复杂度。另外，这个算法的 space 复杂度是多少？

Answer 1

如果我们假设n = mk，时间复杂度将是T(k) = 2T(k/2) + n + n。 n 用于数组复制，n 用于合并，2T(k/2) 用于递归调用。因此，算法的时间复杂度为O(nlog k) = O(mk log(k)).

由于每次将数组的所有值复制入栈，栈深O(log k)，space复杂度为O(n log k) = O(mk log k).

分而治之k-way-merge算法的时间和space复杂度

Time and space complexity of divide and conquer k-way-merge algorithm

arrays

sorting

algorithm

divide-and-conquer