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

Question

我正在阅读Cormen的入门算法。
我不明白为什么合并n/k阵列和k元素在他们每个中的复杂性为O(n*log(n/k))。
我在这里想念的是我们有n/k数组。因此，我们必须执行合并n/(k-1)每次与O(n)上限。
但是我们有一个对数，所以我想我错过了我对合并复杂度的理解。

任何帮助，欢迎。

Answer 1

假设你只可以合并两个数组与合并（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一堆，并让它保持从尚未用尽每个数组中最小数，并在迭代 - 获得结果数组中堆的最小元素。