1

正如标题所示，我想知道合并 k 个大小为 n 的排序数组的下限的证明是什么？我知道界限是 O(kn*log[k])，但是这是如何实现的呢？我尝试与使用决策树对 p 元素数组进行排序进行比较，但我不知道如何实现这个证明。

4

3 回答 3

1

这很容易证明，尝试以合并排序的方式考虑它。要对大小为K*N

的数组进行合并排序，需要O(KN*log(K*N))。

但是我们不必到达大小为1的叶子，因为我们知道当数组大小为N时，它会被排序。为简单起见，我们假设K是 2 的幂。 我们必须除以 2 多少次才能到达大小为 N 的叶子？ K倍！



可视化 在此处输入图像描述


所以你有log(k)步骤，然后必须合并每个步骤成本K N，并且有log(k)步骤。因此，时间复杂度为O(NK (log(K))


证明：
让我们假设它不是一个下限，我们可以做得更好。然后对于任何大小为N*K的未知数组，我们可以将其拆分为 2，直到我们到达大小为 N 的子数组，在Nlog(N)时间内对大小为 N 的每个数组进行合并排序，并且对所有数组进行合并排序K *N*log(N)时间。

在对大小为 N 的 K 个数组进行排序后，我们必须将它们合并到一个更大的大小为N*K的数组中，支付少于O(NK*(log(K))的费用，因为我们假设它不是下限。

最后，您以小于N*K*log(N*K)的复杂度对大小为 N*K 的未知数组进行了排序，这在比较模型中是不可能的。 因此，在合并大小为 N 的 K 个排序数组时
，您无法获得比O(NK*(log(K))更好的结果。

于 2017-10-10T12:58:04.237 回答
1

可能的实施。
让我们创建一个堆数据结构来存储(element, arrayIndex)按元素排序的对。然后

  1. 将具有相应数组索引的每个数组的第一个元素添加到此堆中。
  2. 在每一步中，从堆中删除顶部（最低）对p，添加到结果中，然后将具有索引数组中下一个元素p.element的对插入到堆中（如果它不为空）。(next, p.arrayIndex)p.arrayIndex

为了跟踪“下一个”元素，您需要一个带有k指向相应数组的下一个元素的索引/指针/迭代器的数组。

任何时候堆中最多有k元素，因此堆的insert/remove操作将具有O(log(k))复杂性。每个元素都将从堆中插入和删除一次。元素个数为n*k。总体复杂度为O(n*k*log(k)).

于 2017-10-10T13:25:10.827 回答
0

创建一个大小为 k 的最小堆，用于存储 k 个数组中每个数组的下一项。每个节点还存储它来自哪个数组。通过将堆中的最小值添加到 final_sorted_array 来创建排序数组，然后将数组中的下一个元素添加到堆中。

移除堆的最小值是 O(log k)。您总共有 NK 个元素，因此您执行此 NK 次。最终结果：O(NK log k)。

于 2017-10-10T14:53:01.703 回答