algorithm - 合并排序中合并操作的复杂性

Question

我正在阅读 Cormen 的算法导论。
我不明白为什么将 n/k 数组与每个数组中的 k 元素合并具有 O(n*log(n/k)) 的复杂性。
我在这里缺少的是我们有 n/k 数组。因此，我们必须执行合并 n/(k-1) 次，每次合并 O(n) 上限。
但是我们有一个对数，所以我想我在理解合并复杂性时遗漏了一些东西。

欢迎任何帮助。

Answer 1

假设您只能使用 merge(a,b) 合并两个数组，那么您可以构建一个合并“树”:

a    b      c     d
  ab           cd
       abcd

现在，确实使用此操作您确实在执行 n/k - 1 合并 - 但请注意，大多数合并都是用很少的元素完成的，明显少于 n 每个数组的元素。

如果你仔细计算，你会得到:

2*(n/k)/2 * k + 2*(n/k)/4 * 2k + .... + 1*n

如果你做代数，你会注意到这确实是 n*log(n/k)。

---

另一方面，另一种进行 k 向合并的方法是持有一个大小为 n/k 的堆，并让它持有每个数组中尚未耗尽的最小数字，并在迭代时 - 将堆中的最小元素获取到结果数组。