algorithm - CLRS 算法：在 O(n*lg(n/k)) 中合并 n/k 个子列表，每个子列表大小为 k

Question

这是来自 CLRS 的问题 2-1.b。我不明白如何在 n*lg(n/k) 中合并 n/k 个大小为 k 的数组。我能想出的最佳解决方案是通过在每个子列表的 min 元素中搜索 min 元素来填充大小为 n 的最终数组的每个条目。这导致 O(nk)。在指定时间内完成它的算法是什么？

Answer 1

我刚刚做了这个问题，我想答案如下： 子列表仍然是一次合并两个。1）考虑合并每个“级别”需要多长时间。2）考虑有多少合并操作（您开始的第一个列表下方的“级别”数）。

合并每个级别需要多长时间？每个子列表有 k 个元素，因此有 (n/k) 个子列表。因此元素的总数为 k * (n/k) = n，因此每个级别的合并操作为 theta(n)。

有多少个合并操作（级别）？

If there is 1 sorted sublist: 0
If there are 2 sorted sublists: 1
If there are 4 sorted sublists: 2
If there are 8 sorted sublists: 3
If there are 16 sorted sublists: 4

1 = 2^0
2 = 2^1
4 = 2^2
8 = 2^3
16 = 2^4

所以我们可以制定一个通用规则，格式与上面列出的特定规则相同：

If there are 2^p sorted sublists: p

当我们需要问这个问题"2 to the power 'what?' = m"时，我们需要一个对数。

所以，如果我们问"2 to the power 'what?' = 16?" 答案是log to base 2 of 16 = lg 16 = 4

因此，询问有多少级合并操作与询问“2 次方‘什么？’是一样的。= 米”。我们现在知道答案是log to base 2 of n = lg m。

所以我们现在知道有合并操作的lg m级别，并且每个级别的合并操作都需要n时间。因此总时间为n * lg m = n lg m

请记住，m 是我们要合并的元素数量，在这种情况下，是算法的插入排序部分返回的排序子列表的数量。这是n/k. 所以，总时间为n log (n/k)。