我正在自学CLRS第三版，这是我为所有人服务时遇到的及其答案中最棘手的问题之一。
7.4-5通过利用以下优势，我们可以在实践中缩短快速排序的运行时间当输入被“近”分类时，插入分类的运行时间很快。致电时少于k个元素的子数组上的quicksort，让它简单地返回而无需排序子数组。在对quicksort的顶级调用返回后，运行插入排序在整个阵列上完成排序过程。认为这种排序算法在O(nk+nlg(n/k))预期时间内运行。从理论上讲我们应该如何选择k并在实践中？
如果评估方程nlgn > nk + nlog(n/k)，则得到log k > k。这是不可能的。因此，从理论上讲这是不可能的。但是实际上，插入排序和快速排序涉及恒定的因素。看一下本pdf中讨论的解决方案。您可能要更新您的答案。 。
实际上，答案是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。
一片叶子具有相等的概率，其大小在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可以提供更好的性能。
答案的第二部分相当宽松地使用big-O表示法，因此，为了更精确地选择k，请按照第二个答案中Ankush给出的链接。
我如下解决了该问题，并获得满分。我希望这可以帮助您理解问题。为了澄清一件事，T(N/k)来自以下事实：我们将数组分为k个不同部分，我们正在执行插入排序，即O(k^2)，这是基本情况，因为插入排序会产生预期的结果。
[<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLnN0YWNrLmltZ3VyLmNvbS9CQ0pjOS5wbmcifQ==” alt =“问题的解决方案”> [1