单选题
已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。【中国科技大学1998二、9(2分)】【中科院计算所1998二、9(2分)】
A、
O(nlog
2
n)
B、
O(nlog
2
k)
C、
O(klog
2
n)
D、
O(klog
2
k)
【正确答案】
B
【答案解析】
解析：因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog
2
k)，全部时间下界为O(nlog
2
k)。
提交答案
关闭