为什么K-路合并O（NK ^ 2）？ [英] Why is k-way merge O(nk^2)?

问题描述

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次，第一次作为合并（数组1，阵列-2），第二个为合并（合并（数组1，阵列-2），阵列-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合并与正*的平均尺寸（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屋！