单选题
基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。
A、
O(nlog
2
n)
B、
O(log
2
n)
C、
O(n)
D、
O(n
2
)
【正确答案】
A
【答案解析】
解析：此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log
2
(n!)次比较。 由Stirling公式可知，log
2
(n!)≈nlog
2
n一1．44n+O(log
2
n)。所以基于关键字比较的分类时间的下界是O(nlog
2
n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。
提交答案
关闭