5

我正在自学 CLRS 第 3 版，这是我遇到的更棘手的问题之一，以及它作为对所有人的服务的答案。

7.4-5 我们可以在实践中利用插入排序在输入“接近”排序时的快速运行时间来提高快速排序的运行时间。在元素少于k元素的子数组上调用快速排序时，让它简单地返回而不对子数组进行排序。在对快速排序的顶级调用返回后，对整个数组运行插入排序以完成排序过程。认为这种排序算法在O(nk+nlg(n/k))预期时间内运行。我们应该如何选择k，无论是在理论上还是在实践中？

4

3 回答 3

3

如果你评估方程nlgn > nk + nlog(n/k)，你会得到log k > k. 这是不可能的。所以理论上是不可能的。但在实践中，插入排序和快速排序涉及到一些不变的因素。看看这个pdf中讨论的解决方案。您可能想更新您的答案。.

于 2012-09-08T13:21:19.520 回答
2

其实，答案是k = 8。

你得到的算法是两个匿名函数的组合，一个是O(nk)，另一个是O(n lg n/k)。那些匿名函数隐藏了平均大小写常量。插入排序在n^2/4平均情况下及时运行，随机快速排序在1.386 n lg n平均情况下运行。我们想找到一个值，k它使nk/4 + 1.386( n lg n/k )等于的值最小化nk/4 + 1.386 n lg n - 1.386 n lg k。这意味着找到函数的最大值1.386 lg k - k/4。该最大值出现在k = 8。

于 2013-04-25T10:08:57.287 回答
0

1叶子的大小在到之间的概率相等k。
所以一片叶子的预期大小是k/2。
如果叶子的预期大小是，k/2那么我们期望n/(k/2)=(2n)/k这样的叶子。
为简单起见，假设我们期望n/k这样的叶子，并且每个叶子的预期大小是k。
的预期运行时间INSERTION-SORT为O(n^2)。
我们在练习 5.2-5 和问题 2-4c 中发现了这一点。
所以使用的预期运行时间INSERTION-SORT是O((n/k)*(k^2))=O(nk)。
如果我们期望我们的分区组的大小k，那么递归树的高度应该是因为我们期望更早lgn-lgk=lg(n/k)停止。 有lgk
O(n)递归树每一层的操作。
这导致我们O(nlg(n/k))。
我们得出的结论是预期的运行时间是O(nk+nlg(n/k))。

理论上，我们应该选择k=lgn，因为这样我们可以获得 的最佳预期运行时间O(nlgn)。

在实践中，我们应该选择k一个lgn能够为我们提供比运行更好的性能的值RANDOMIZED-QUICKSORT。

答案的第二部分非常松散地使用大 O 表示法，因此要更精确地选择k，请按照 Ankush 在第二个答案中给出的链接进行操作。

于 2012-03-05T17:22:06.657 回答