合并大小为n的k个排序数组的下界

Question

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

Answer 1

这很容易证明，请尝试以合并排序的方式考虑它。

要合并排序大小为的数组，K * N需要O（KN * log（K * N））。

但是我们没有达到叶子大小的，因为我们知道，当数组大小ň将垃圾分类。为了简单起见，我们将假设K是2的幂。

我们必须用2除以多少次才能达到尺寸为N的叶子？
K次！

可视化

所以，你必须日志（k）的步骤，然后将具有合并的每个步骤成本ķÑ，并且有日志（k）的步骤。因此，时间复杂度为O（NK（日志（K））

证明：
让我们假设它不是一个下限，我们可以取得更好的那么对于大小的任何未知的数组ñ* K我们可以在2，直到我们达到尺寸ñ的子阵列它分割，合并排序的每个的大小为N的阵列的在NLOG（N）对于所有阵列K个时和在总* N * log（N） time。

在将K个大小为N的数组排序后，我们必须将它们合并成一个大小较大的数组，大小为N * K，支付小于O（NK *（log（K）），因为我们假设它不是下限。

最后，您在复杂度小于N * K * log（N * K）的情况下对大小为N * K的未知数组排序，这在比较模型中是不可能的。
因此，你无法实现优于O（NK *（日志（K））而合并K个排序的大小N的数组

Answer 2

可能的实现。
让我们创建一个储存对(element, arrayIndex)一个heap data structure然后

1. 将每个数组的第一个元素与相应的数组索引添加到这个堆中。
2. 在每个步骤中，除去顶部（最低）对p从堆中，添加p.element到的结果，并插入到堆的一对(next, p.arrayIndex)与从阵列的下一个元素与p.arrayIndex索引（如果非空） 。

为了跟踪'next'元素，你需要一个包含指向相应数组下一个元素的指数/指针/迭代器的数组。

将有在任何时间在堆至多k元素，因此堆的insert/remove操作将有O(log(k))复杂性。每个元素都将被插入并从堆中移除一次。元素的数量是n*k。整体复杂度为O(n*k*log(k))。

Answer 3

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

删除堆的最小值为O（log k）。你总共有NK元素，所以你做这个NK时代。最终结果：O（NK log k）。