1

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

4

1 回答 1

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)

于 2015-11-29T00:05:04.477 回答