合并排序中合并操作的复杂性
Complexity of merge operation in merge sort
我正在阅读 Cormen 的算法导论。
我不明白为什么将 n/k 数组与每个数组中的 k 元素合并具有 O(n*log(n/k)).
的复杂性
我在这里缺少的是我们有 n/k 个数组。因此，我们必须执行合并 n/(k-1) 次，每次合并 O(n) 上限。
但是我们有一个对数，所以我想我在理解合并复杂性时遗漏了一些东西。
欢迎任何帮助。
假设您只能使用 merge(a,b) 合并两个数组，那么您可以构建 "tree" 个合并：
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 的堆，并让它持有每个数组中尚未耗尽的最小数字，并在迭代时- 获取堆中最小的元素到结果数组。
我正在阅读 Cormen 的算法导论。
我不明白为什么将 n/k 数组与每个数组中的 k 元素合并具有 O(n*log(n/k)).
的复杂性
我在这里缺少的是我们有 n/k 个数组。因此，我们必须执行合并 n/(k-1) 次，每次合并 O(n) 上限。
但是我们有一个对数，所以我想我在理解合并复杂性时遗漏了一些东西。
欢迎任何帮助。
假设您只能使用 merge(a,b) 合并两个数组，那么您可以构建 "tree" 个合并：
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 的堆，并让它持有每个数组中尚未耗尽的最小数字，并在迭代时- 获取堆中最小的元素到结果数组。