为什么迭代k方式合并O（nk ^ 2）？ [英] Why is iterative k-way merge O(nk^2)?

问题描述

k路合并是将k个大小为n的排序数组作为输入的算法。它输出所有元素的单个排序数组。

k-way merge is the algorithm that takes as input k sorted arrays, each of size n. It outputs a single sorted array of all the elements.

通过使用归并排序算法中心的合并例程将数组1合并为数组2，可以做到这一点。然后将数组3移到此合并的数组，依此类推，直到所有k个数组都合并。

It does so by using the "merge" routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged.

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

I had thought that this algorithm is O(kn) because the algorithm traverses each of the k arrays (each of length n) once. Why is it O(nk^2)?

推荐答案

因为它不会遍历k个数组中的每一个。第一个数组被遍历k-1次，第一个作为merge（array-1，array-2），第二个作为merge（merge（array-1，array-2），array-3）...依此类推

Because it doesn't traverse each of the k arrays once. The first array is traversed k-1 times, the first as merge(array-1,array-2), the second as merge(merge(array-1, array-2), array-3) ... and so on.

结果是k-1合并，平均大小为n *（k + 1）/ 2，给出了O（n *（k ^ 2- 1）/ 2）是O（nk ^ 2）。

The result is k-1 merges with an average size of n*(k+1)/2 giving a complexity of O(n*(k^2-1)/2) which is O(nk^2).

您犯的错误是忘记了合并是串行而不是并行完成的，因此数组是并非所有尺寸都为n。

The mistake you made was forgetting that the merges are done serially rather than in parallel, so the arrays are not all size n.

这篇关于为什么迭代k方式合并O（nk ^ 2）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！