单选题
使用递归的快速排序算法时,为了保证排序过程的时间复杂度不超过O(nlog
2
n),必须做到______。
A、
每次序列的划分应该在线性时间内完成
B、
每次归并的两个子序列长度接近
C、
每次归并在线性时间内完成
D、
以上全是
【正确答案】
C
【答案解析】
[解析] 递归的快速排序算法属于分治法,理想情况是它把待排序的序列划分为两个规模相近的子序列(达到n/2)。这样每次把问题的规模缩减一半,递归深度达到log
2
n。
提交答案
关闭