为什么迭代的k路归并算法时间复杂度为O(nk^2)？

Question

k路归并是一种算法，它将k个大小为n的排序数组作为输入，并输出一个包含所有元素的单个已排序数组。

这是通过使用与合并排序算法中心相同的“合并”例程来将第1个数组合并到第2个数组，然后将第3个数组合并到此合并数组中，以此类推，直到所有k个数组都合并为止。

我曾认为该算法的时间复杂度为O(kn)，因为该算法遍历每个长度为n的k个数组各一次。但为什么时间复杂度是O(nk^2)呢？

- dangerChihuahua007

---

可以使用堆或选择树在每个阶段从k个可能的选择中选择下一个元素，以获得O(n k log k)的时间复杂度。例如，Knuth的《计算机程序设计艺术》卷二排序和搜索章节5.4.1。 - mcdowella

算法选择数组的一对，因此您有comb(k 2) = k * (k-1) /2。由于每个数组的大小为n且合并需要O(n)，因此您得到O(nk^2)。 - jassinm

你可以使用队列，时间复杂度将为O(n log k)，其中n是整数的数量，k是已排序数组的数量。 - Dejell

@Dejel 遍历所有元素将需要 O(nk) 的时间。使用堆，我们可以得到 O(nklogk) 的时间复杂度。您能详细说明如何实现 O(nlogk) 的时间复杂度吗？ - claudius

Answer 1

因为它没有遍历 k 个数组，每个数组只被遍历了 k-1 次。第一个数组被遍历了 k-1 次，第一次是合并 (array-1,array-2)，第二次是合并 (merge(array-1, array-2), array-3) ... 以此类推。

结果是 k-1 次合并，平均大小为 n*(k+1)/2，复杂度为 O(n*(k^2-1)/2)，即 O(nk^2)。

你犯的错误是忘记了这些合并是串行完成而不是并行完成，因此这些数组的大小不都是 n。

- Recurse

---

你如何获得平均大小？ - bneil

第一次合并的大小为2n（两个大小为n的数组）。第二次合并的大小为3n（大小为2n的累积数组和大小为n的另一个数组）。你应该能够看到第k次合并的大小为(k + 1)n。平均大小约等于这个值的一半，即n(k+1)/2，任何残留的项都不会影响O()分析。 - Recurse

Answer 2

事实上，在最坏的情况下，第一个数组将进行n次比较，第二个数组将进行2n次比较，第三个数组将进行3n次比较，以此类推，直到第(k - 1)n个数组。
因此，现在复杂度变得简单了。

n + 2n + 3n + 4n + ... + (k - 1)n
= n(1 + 2 + 3 + 4 + ... + (k - 1))
= n((k - 1)*k) / 2
= n(k^2 - k) / 2
= O(nk ^ 2)

:-)

- Gopichand

---

我知道这是一个无知的问题，但你能告诉我如何从第2步到第3步吗？换句话说，为什么在(1...k-1)上求和等于((k-1)*k)/2？这是人们所说的高斯长数列加法技巧的正式化吗？ - bhagerty

@user3208862：这是因为求和规则，当你计算(1+2+3+...k)时，它等于k(k+1)/2。请参考https://en.wikipedia.org/wiki/Summation。 - Ahmed_A

Answer 3

这样怎么样：

步骤1： 合并数组（1和2），数组（3和4），以此类推。（k/2个长度为2n的数组合并，总工作量为kn）。

步骤2： 合并数组（1,2和3,4），数组（5,6和7,8），以此类推。（k/4个长度为4n的数组合并，总工作量为kn）。

步骤3： 重复…

会有log(k)个这样的“步骤”，每个步骤的工作量为kn。因此总工作量为O(k.n.log(k))。

即使我们只是对数组的所有元素进行排序，我们仍然可以在O(k.n.log(k.n))的时间内合并所有元素。

- JackOfNullTrades

---

说实话，我认为这个自底向上的合并比OP问题中的那个好多了。 - Jackson Tale

Answer 4

k路归并算法是一种输入k个大小为n的已排序数组，输出所有元素的单个排序数组的算法。我曾认为该算法的时间复杂度为O(kn)。

我们可以通过反证法来证明它不是O(kn)。定义一个排序算法用于m个项目，其中使用k=m和n=1的算法。根据假设，排序算法在O(m)时间内成功。这与事实矛盾，已知任何排序算法的最坏情况至少为O(m log m)。

- Colonel Panic

---

以防有人偶然跌入此处，nlogn 的最坏情况排序时间仅适用于基于比较的排序算法。例如计数或桶排序等算法不是比较排序，并且仅在满足输入的某些限制时才适用。例如，快速查看计数排序可以告诉您，如果任何元素的值（例如100）大于数组大小，则会超出范围。 - fkl

Answer 5

您无需每次逐个比较项目。您只需在已排序的集合中维护最近的K个项目。您删除最小的并用其下一个元素替换它。这应该是n.log(k)。

相关文章。免责声明：我参与了撰写

- nakhli

---

正确。但是您需要提到您在那里使用堆（例如队列）。 - Dejell

这是我在回答中所说的“排序集合”的意思。实际上，你需要一个排序的多重集合。堆是其中一种可能的实现方式。 - nakhli

对于您的堆，最终将向结构中插入nk-1个元素。由于插入成本为O(log(k))，因此整个合并的复杂度应该是O(nklog(k))，而不是您所说的nlog(k)。正如问题所述，n是块的大小。如果我们将N视为总大小，则相对于N的复杂度为O(Nlog(k))。 - Horia Toma

Answer 6

1) 你有k个已排序的数组，每个数组的大小均为n。因此元素的总数为k * n。

2) 取出所有k个数组的第一个元素，并创建一个序列。然后找到这个序列中的最小值。将此最小值存储在输出数组中。查找k个元素的最小值所需的比较次数为k-1次。

3) 因此，总比较次数为：
=（每个元素的比较次数）* 元素的数量
=（k-1）* k * n
= k ^ 2 * n //近似值

- user2263353

Answer 7

一种常见的实现方式是为每个排序数组 {i_1, i_2, i__k} 保留一个索引数组。在每次迭代中，算法从这 k 个数组中找到下一个最小元素，并将其存储在输出数组中。由于您将对 k 个数组进行 kn 次迭代和扫描，总复杂度为 O(k^2 * n)。

以下是伪代码：

Input: A[j] j = 1..k : k sorted arrays each of length n
Output: B : Sorted array of length kn

// Initialize array of indexes
I[j] = 0 for j = 1..k

q = 0

while (q < kn):
    p = argmin({A[j][I[j]]}) j = 1..k           // Get the array for which the next unprocessed element is minimal (ignores arrays for which I[j] > n)
    B[q] = A[p][I[p]]
    I[p] = I[p] + 1
    q = q + 1

- smichak

Answer 8

1. 您有k个数组，每个数组有n个元素。这意味着总共有k*n个元素。

2. 将其视为一个k*n的矩阵。要将第一个元素添加到合并/最终数组中，您需要比较k个数组的头部。这意味着对于最终数组中的一个元素，您需要进行k次比较。

因此，根据1和2，对于Kn个元素，所需的总时间为O(kk*n)。

- busybug91

Answer 9

对于那些想要了解细节或需要一些帮助的人，我将扩展Recurse的答案和后续评论

• 我们只需要k-1次合并，因为最后一个数组不会与任何东西合并
• 算术序列求和公式很有帮助；Sn=n(a1 + an)2

通过k个具有n个元素的数组的前4次合并进行步进

+-------+-------------------+-------------+
| Merge | Size of new array |    Note     |
+-------+-------------------+-------------+
| 1     | n+n  = 2n         | first merge  |
| 2     | 2n+n = 3n         |             |
| 3     | 3n+n = 4n         |             |
| 4     | 4n+n = 5n         |             |
| k-1   | (k-1)n+n = kn     | last merge  |
+-------+-------------------+-------------+

为了找到平均大小，我们需要将所有大小相加并除以合并次数（k-1）。使用求和前n项的公式Sn=n(a1 + an)2，我们只需要第一个和最后一个项：

• a1=2n（第一项）
• an=kn（最后一项）

我们想要对所有项求和，因此n=k-1（我们拥有的项数）。代入数字，我们得到所有项的总和公式 Sn = ( (k-1)(2n+kn) )/2 然而，为了找到平均大小，我们必须除以项数（k-1）。这会消去分子中的k-1，留下平均大小为 (2n + kn)/2 现在我们有了平均大小，我们可以将其乘以合并的数量，即k-1。为了使乘法更容易，忽略/2，只需将分子相乘即可：

  (k-1)(2n+kn)
= (k^2)n + kn - 2n

此时您可以重新引入/2，但是没有必要，因为显然主导项是(k^2)*n

- Jack