59

k-way merge 是将 k 个排序数组作为输入的算法，每个数组的大小为 n。它输出所有元素的单个排序数组。

它通过使用合并排序算法的核心“合并”例程将数组 1 合并到数组 2，然后将数组 3 合并到这个合并的数组，依此类推，直到所有 k 个数组合并。

我曾认为这个算法是 O(kn)，因为该算法遍历每个 k 个数组（每个数组的长度为 n）一次。为什么是 O(nk^2)？

4

9 回答 9

67

因为它不会遍历每个 k 数组一次。第一个数组被遍历 k-1 次，第一个为 merge(array-1,array-2)，第二个为 merge(merge(array-1, array-2), array-3) ... 以此类推.

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

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

于 2012-06-14T03:31:45.903 回答
47

实际上，在最坏的情况下，第一个数组将进行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)

:-)

于 2013-02-14T12:34:55.110 回答
16

这个怎么样：

第 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(knlog(k))。

即便如此，如果我们只对数组的所有元素进行排序，我们仍然可以在 O(knlog(kn)) 时间内合并所有元素。

于 2013-12-06T02:16:06.387 回答
7

k-way merge 是将 k 个排序数组作为输入的算法，每个数组的大小为 n。它输出所有元素的单个排序数组。

我原以为这个算法是 O(kn)

我们可以通过反证来反驳这一点。为 m 个项目定义一个排序算法，该算法使用 k=m 和 n=1 的算法。根据假设，排序算法在 O(m) 时间内成功。矛盾的是，众所周知，任何排序算法的最坏情况至少为 O(m log m)。

于 2013-07-13T16:12:37.010 回答
6

您不必每次都逐一比较项目。您应该简单地维护排序集中最近的 K 项。您删除最小的并用它的下一个元素替换它。这应该是 n.log(k)

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

于 2013-02-06T23:53:54.783 回答
4

1）你有k个排序数组，每个大小为n。因此元素总数 = k * n

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

3) 因此，比较总数
= (comparisons/element) * 元素数
= (k - 1) * k * n
= k^2 * n // 大约

于 2013-04-09T19:42:02.170 回答
3

一个常见的实现为 k 个排序数组 {i_1, i_2, i__k} 中的每一个保留一个索引数组。在每次迭代中，算法从所有 k 个数组中找到最小的下一个元素并将其存储在输出数组中。由于您正在进行 kn 次迭代并每次迭代扫描 k 个数组，因此总复杂度为 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
于 2012-06-14T04:14:50.210 回答
0

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

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

因此，从 1 和 2 开始，对于 K n 个元素，所花费的总时间为 O(k k*n)。

于 2015-03-13T05:58:25.590 回答
0

对于那些想了解细节或需要帮助的人，我将扩展 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

于 2020-11-25T19:32:04.620 回答