gpt4 book ai didi

arrays - 合并排序数组,最佳时间复杂度是多少?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:39:25 26 4
gpt4 key购买 nike

我有 m 个数组,每个数组的长度为 n。每个数组都已排序。我想创建一个长度为 m*n 的数组,其中包含已排序的先前数组的所有值(包括重复值)。我必须合并这些数组..

我认为最优的时间复杂度是m*n*log(m)

这是算法的草图..

我创建了一个长度为 m 的支持数组 H,其中包含每个数组第一个元素的所有值。

然后我对该数组进行排序 (m log m),并将最小值移至输出数组。

然后我将移动的值替换为下一个值,从它被获取的数组中。实际上我并没有替换它,而是将它插入正确(排序)的位置。我认为这需要 log m。

然后我对所有 m*n 值重复此操作...因此 m*n*log m

我的问题.. 你能想到一个更有效的算法吗?如果 mnlogm 实际上是最优的,您至少可以想出一个更简单、更优雅的算法吗?

最佳答案

复杂度是对的!但是,您的算法思想有一个小缺陷:您不能在 log m 中的排序数组中插入一个项目。您可以在这种复杂性中使用二进制搜索找到它的位置,但您可能必须四处移动元素才能将其实际放置在那里。要解决此问题,您可以改用堆数据结构!

多路合并(这是您的算法的通用名称)通常使用另一种“合并”数据结构来实现:锦标赛树。您可以在 Knuth 的“计算机编程艺术”(关于排序的章节,iirc)中找到描述。在这种特定情况下,与堆相比,它在理论上和实践中具有较低的常数因子。

如果您想查看实现,我很确定 GNU C++ 标准库并行扩展中的并行多路合并是通过这种方式实现的。

编辑:我引用了错误的书,现在已修复。

关于arrays - 合并排序数组,最佳时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5116043/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com