algorithm - CLRS 算法 : Merge n/k sublists each of size k in O(n*lg(n/k))

Question

这是来自 CLRS 的问题 2-1.b。我不明白如何在 n*lg(n/k) 中合并每个大小为 k 的 n/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 的‘什么？’的幂= m"，那么我们需要一个对数。

所以，如果我们问 “2 的‘什么？’次方= 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)。