我正在自学CLRS第三版，这是我遇到的最棘手的问题之一，以及它的答案，作为对所有人的服务。
7.4-5我们可以在实践中利用插入排序在其输入"接近"排序时的快速运行时间。打电话时对元素少于k的子数组进行快速排序，让它简单地返回对子数组进行排序。在对快速排序的顶级调用返回后，运行插入排序在整个数组上完成排序过程。认为这种排序算法在CCD_ 2预期时间内运行。理论上我们应该如何选择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时间内运行。我们想要找到CCD_ 11的值，该值最小化等于CCD_ 13的CCD_。这意味着找到函数CCD_ 14的最大值。该最大值出现在k = 8。
叶大小在1到k之间的概率相等
因此，一个叶子的预期大小是k/2
如果期望的叶的大小是k/2，那么我们期望O(nk+nlg(n/k))0这样的叶
为了简单起见，假设我们期望n/k这样的叶子，并且每个叶子的期望大小是kINSERTION-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))
我们得出预期运行时间为CCD_ 32。
理论上，我们应该选择k=lgn，因为这样我们可以获得O(nlgn)的最佳预期运行时间。
在实践中，我们应该将k选择为lgn周围的一个值，该值比仅运行RANDOMIZED-QUICKSORT提供更好的性能。
答案的第二部分非常松散地使用了big-O表示法，因此为了更准确地选择k，请按照Ankush在第二个答案中给出的链接进行操作。