Avi*_*hen 5 algorithm complexity-theory quicksort insertion-sort clrs
我是自学CLRS第3版,这是我遇到的更难的问题之一,以及它作为一项服务给所有人的答案.
7.4-5
当输入"近似"排序时,我们可以利用插入排序的快速运行时间来改善快速排序的运行时间.在使用少于k元素的子数组上调用quicksort时,让它只返回而不对子数组进行排序.在对quicksort返回顶级调用之后,对整个数组运行插入排序以完成排序过程.认为这种排序算法在O(nk+nlg(n/k))预期的时间内运行.我们应该如何k在理论和实践中选择？