算法问题2
尽管合并排序的最坏情况运行时间为O(nlgn),插入排序的最坏情况是O(n2),但插入排序中的常数因子使得它在n较小时,运行的更快一些。因此,在合并排序算法中,当子问题足够小时,采用插入排序就比较合适了。考虑对合并排序做这样的修改,即采用插入排序策略,对n/k个长度为k的子列表进行排序,然后,再用标准的合并机制将它们合并起来,此处k是一个待定的值。
A.证明在最坏情况下,n/k个子列表(每一个子列表的长度为k)可以用插入排序在O(nk)时间内完成。
B.证明这些子列表可以在O(nlg(n/k))最坏情况时间内合并完成。
C.如果已知修改后的合并排序算法的最坏情况运行时间为O(nk+nlg(n/k)),要使修改后的算法具有与标准合并算法一样的渐近运行时间,k的最大渐近值(即大O形式)是什么?
D.在实践中,k的值应该如何选取?
AB两个问题我会,但是CD就没有什么思路了。