2

这是 Cormen 的算法介绍中的一个问题。但这不是家庭作业问题，而是自学。

有一个长度数组n。考虑对合并排序的修改，其中n/k每个长度k的子列表使用插入排序进行排序，然后使用合并机制进行合并，其中 k 是要确定的值。

n和之间的关系k尚不清楚。数组的长度为n。均值的k子列表等于数组的元素。因此，这只是一个限制，在此限制中停止使用合并排序的数组拆分，而是使用插入排序，因为它的常数因子较小。n/kn * (n/k)nk

我能够进行数学证明，证明修改后的算法在Θ(n*k + n*lg(n/k))最坏情况下也有效。现在这本书继续说

根据 Θ 表示法，找到这个修改后的算法与标准归并排序具有相同运行时间k的函数的最大值。n在实践中我们应该如何选择k？

现在这让我想了很多时间，但我什么也想不出来。我试图解决

n*k + n*lg(n/k) = n*lg(n)为一段关系。我认为找到两个运行时间的相等性会给我带来限制，并且可以使用简单的命中和试验来检查更大的限制。

我这样解决了

n k + n lg(n/k) = n  lg(n)

k + lg(n/k) = lg(n)

lg(2^k) + lg(n/k) = lg(n)

(2^k * n)/k = n

2^k = k

但这给了我2 ^ k = k没有任何关系的信息。有什么关系？我想我可能用错误的方程式来寻找关系。

我可以实现该算法，我想在函数中添加一条if (length_Array < k)语句（合并排序实现的 Github 链接）来调用插入排序就足够了。但是我该如何选择merge_sortk但是在现实生活中

4

2 回答 2

2

嗯，这是一个数学最小化问题，要解决它，我们需要一些基本的微积分。

我们需要找到kfor which的值d[n*k + n*lg(n/k)] / dk == 0。

我们还应该检查边缘情况，即k == n和k == 1。

的值的候选k将给出最小结果n*k + n*lg(n/k)是所需范围内的最小值，因此是 的最佳值k。

附上，求解导数方程：

d[n*k + n*lg(n/k)] / dk = d[n*k + nlg(n) - nlg(k)] / dk
= n + 0 - n*1/k = n - n/k 
=>
n - n/k = 0 => n = n/k => 1/k = 1 => k = 1

现在，我们有了候选：k=n，k=1。对于 k=n，我们得到O(n^2)，因此我们得出最优结论k是k == 1​​。

请注意，我们从大 Theta 中找到了函数的导数，而不是在使用所需常量的确切复杂度函数上。
在精确的复杂度函数上执行此操作，所有常量可能会产生一些不同的最终结果 - 但解决它的方法几乎相同，只是从不同的函数中获取导数。

于 2013-08-07T13:18:52.053 回答
1

也许k应该是lg(n)

theta(nk + nlog(n/k))有两项，我们假设k>=1，所以第二项小于nlog(n)。

只有当k=lg(n)，整个结果是theta(nlog(n))

于 2020-02-15T02:13:27.237 回答