为什么迭代k-way合并O(nk ^ 2)？

Question

k-way merge是一种算法,它采用大小为n的输入k排序数组.它输出所有元素的单个排序数组.

它通过使用合并排序算法中心的"合并"例程将数组1合并到数组2,然后将数组3合并到此合并数组,依此类推,直到所有k个数组合并为止.

我原以为这个算法是O(kn),因为算法遍历每个k个数组(每个长度为n)一次.为什么是O(nk ^ 2)？

Answer 1

因为它不会遍历每个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.

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)

:-)

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)这样的"Steps",每个都有kn工作.因此,完成的总工作量= O(knlog(k)).

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

Answer 4

我不同意其他答案.您不必每次比较1到1的项目.您应该只是在排序集中维护最新的K项.您删除最小的并通过其下一个元素重新发送它.这应该是n.log(k)

相关文章.免责声明:我参与了写作

Answer 5

k-way merge是一种算法,它采用大小为n的输入k排序数组.它输出所有元素的单个排序数组.

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

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