algorithm - 使用合并过程对小型数组进行插入排序 :

Question

考虑问题:

尽管合并排序在 Θ(nlgn) 最坏情况下运行，而插入排序在 Θ(n^2) 最坏情况下运行 时间，插入排序中的常数因子使得它对于小的n更快。因此，当子问题变得足够小时，在合并排序中使用插入排序是有意义的。 考虑对合并排序的修改，其中使用插入排序对长度为 k 的 n/k 子列表进行排序，然后使用标准合并机制进行合并，其中 k 为待定值。

问题证明子列表可以在Θ(n lg(n/k))最坏情况下合并:

我的解决方案:

将 n/k 个子列表合并为 n/2k 需要 Θ(n) 次

将 n/2k 个子列表合并到 n/4k 需要 Θ(n) 次

...

要将 2 个子列表合并为 1 个，需要 Θ(n) 次

然后我正在为进一步的步骤而苦苦挣扎，我查看了解决方案:

我们有lg(n/k)这样的合并，所以将n/k个子列表合并成一个列表需要 Θ(n lg(n/k)) 最坏情况时间。

我有两个问题:

1)他们如何结束 lg(n/k) 合并？请澄清计算结果？

2)为什么最后的结果是Θ(n lg(n/k))？

Answer 1

您似乎非常接近实际答案。我相信您查找的答案的措辞让您更难理解，因为我认为所需的单个合并总数不是 lg(n/k)。我认为答案指的是在我们最终得到排序列表之前所需的合并步骤的数量。

但是，让我们继续构建您的推理，而不是答案。合并两个长度为 k 的列表具有 O(k) 时间复杂度。要将 n/k 这样的列表合并到 n/(2k) 列表中，我们将执行 n/(2k) 复杂度合并 O(k) 每个，导致总体 O(n) 复杂性，正如您提到的。

您可以将此逻辑扩展到下一个步骤，其中n/(2k) 列表合并到n/(4k)，并声明第二步也具有 O(n) 复杂性。事实上，每个合并步骤，都将花费 O(n) 时间。

接下来要做的是估计我们有多少合并步骤。我们从 n/k 列表开始，在第一步之后我们获得了 n/(2k) 列表。之后，在每一步中，列表的数量减半，直到只剩下 1 个列表，这就是我们的结果。 (即排序列表)好吧，你认为我们必须将 n/k 除以 2，直到得到 1 为止？这正是 log(n/k) 的意思，不是吗？因此，将有 log(n/k) 这样的合并步骤，每个步骤都需要 O(n)。

因此，整个过程的时间复杂度为O(nlog(n/k))。