4

假设我们有k排序数组（每个大小n），在这种情况下使用优先级堆比传统合并（类似于合并排序中使用的）更好，反之亦然？

优先队列方法：在这种方法中，我们有一个最小堆大小k（最初，每个数组的第一个元素被添加到堆中）。我们现在删除 min 元素（从输入数组之一），将其放入最终数组并从同一个输入数组中插入一个新元素。这种方法需要O(kn log k)时间和O(kn)空间。注意：它占用O(kn)空间，因为这是最终数组的大小，并且在计算渐近空间复杂度时，它决定了堆的大小。

传统合并：在这种方法中，我们合并前 2 个数组以获得大小为的排序数组2n。我们对所有输入数组重复此操作，并且在第一遍之后，我们获得k/2每个大小为的排序数组2n。我们重复这个过程，直到我们得到最终的数组。每次比较都有一个时间复杂度，O(kn)因为每次比较后都会将一个元素添加到相应的输出数组中。我们有 log k 通行证。因此，总时间复杂度为O(kn log k)。而且由于我们可以在每次传递后删除输入数组，因此在任何时候使用的空间都是O(kn).

正如我们所见，两种方法的渐近时间和空间复杂度完全相同。那么，我们究竟什么时候更喜欢其中一个呢？我知道对于外部排序，优先队列方法更好，因为您只需要O(k)内存空间，并且您可以从磁盘读取和写入每个元素。但是当我们有足够的内存时，这些方法如何相互叠加呢？

4

1 回答 1

3

无论哪种方式，比较+移动的操作总数都大致相同。k-way 合并做更多的比较但更少的移动。我的系统有一个 8 路缓存（Intel 3770K 3.5 ghz），在 4 路合并排序的情况下，允许 4 行缓存用于 4 个输入运行和 1 行缓存用于合并输出运行。在 64 位模式下，有 16 个寄存器可用于工作变量，其中 8 个用于指向每个“运行”的当前和结束位置的指针（编译器优化）。

在我的系统上，我比较了 4 路合并（无堆，每个移动的元素约 3 次比较）与 2 路合并（每次移动约 1 次比较，但通过次数是两倍），4 路的比较次数是 1.5 倍，但是移动次数的 0.5 倍，所以操作次数基本相同，但是 4 路由于缓存问题快了大约 15%。

我不知道 16 个寄存器是否足以让 6 路合并稍微快一点，而 16 个寄存器是否不足以让 8 路合并（一些工作变量是基于内存/缓存的）。尝试使用堆可能无济于事，因为堆将基于内存/缓存（不是基于寄存器）。

k-way 合并主要用于外部排序，其中比较时间被忽略，因为移动的开销要大得多。

于 2018-11-18T00:20:23.983 回答