代码之家 › 专栏 › 技术社区 › Liana78

查找和最小化合并排序算法运行时分析

mergesort complexity-theory algorithm arrays java

Liana78 · 技术社区 · 6 年前

假设我有一个大小为n的数组,我想将它预言为k个大小为n/k的新数组- 此步骤的运行时间可能是多少****我想,当我们将一个数组拆分为2时,我们会将其视为2^x=n=>x=日志N=>O(log n)那么这里也一样:k^(n/k)=n=>n/k=日志n****但下一步是什么?

现在,我在每个k数组上运行冒泡排序算法-O(n^2),并在所有k个数组上使用合并算法来生成大小为n的排序数组,假设合并复杂度为O(kn)。

此外,我不想找到一个K,这样我就可以最小化算法的运行时间,我该怎么做呢?我认为对运行时函数求导并找到它的最小值就可以了,这是正确的方法吗?

2 回复 | 直到 6 年前

Jim Mischel 6 年前

“合并排序”将数组依次拆分为较小的片段,直到它变成一组2元素子数组。然后,它开始在连续较大的子阵列上应用合并算法。

假设您有一个由16个元素组成的数组。合并排序的合并方式如下:

8 merges of two 1-item subarrays
4 merges of two 2-item subarrays
2 merges of two 4-item subarrays
1 merge of two 8-item subarrays

有四个(对数 _2. (16) )通过,并在每次通过时检查每个项目。每次通过为O(n)。因此,此合并排序的运行时间是O(n*log _2. (n) )。

现在,假设您有一个包含81个项目的数组,并且您希望使用3路合并排序来合并它。现在您有了以下合并序列:

27 merges of three 1-item subarrays (gives 27 3-item subarrays)
 9 merges of three 3-item subarrays (gives 9 9-item subarrays)
 3 merges of three 9-item subarrays (gives 3 27-item subarrays)
 1 merge of three 27-item subarrays

有四个(对数 _3. (81))通过。每次合并都是O(m*log _2. (k) ),其中m是要合并的项目总数,k是列表数。因此,第一个过程有27个合并,可以进行3*log _2. (3) 比较。下一个过程有9个合并,执行9*log _2. (3) 比较等。最终的结果是总合并为O(n*log _3. (n) *日志 _2. (3) ()

您可以看到,三向合并排序允许您进行较少的传递(16个项目的三向合并排序只需要三次传递),但每次传递都会稍微贵一些。您需要确定的是:

n*日志 _K (n) *日志 _2. (k) <n*日志 _2. (n)

哪里 k 要将阵列拆分为的子阵列数。我会让你算算的。

不过,你必须小心,因为渐近分析没有考虑现实世界的影响。例如,双向合并非常简单。当您转到k路合并时,其中k>2,您最终不得不使用堆或其他优先级队列数据结构,这会带来相当大的开销。因此,即使上面的数学告诉您,3路合并排序应该更快,您也需要将其与标准的2路合并进行比较。

使现代化

你说得对。如果你简化方程,你最终得到的方程是相同的。因此,无论k的值是多少,计算复杂度都是相同的。

这很有意义,因为如果k=x,那么最终会得到堆排序。

因此,您必须确定是否存在这样一个点,即合并开销(随着k的增加而增加)被减少的过程数所抵消。你可能需要根据经验来确定这一点。

btilly 6 年前

传统上,我们使用mergesort进行外部排序算法,这个问题的答案主要取决于一个事实。mergesort需要从多个文件流式传输数据并写入单个文件。瓶颈在于流媒体,而不是CPU。如果您试图一次从一个磁盘上的太多位置进行流式处理,则该磁盘会发生故障并开始进行随机搜索。随机搜索的吞吐量很糟糕。

硬件上的正确答案会有所不同(尤其是在使用SSD驱动器的情况下),但是 traditional Unix sort 以16路合并作为合理违约解决。