基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

admin2019-08-15 34

问题基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

选项 A、O(nlog₂n)
B、O(log₂n)
C、O(n)
D、O(n²)

答案A

解析此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log₂(n!)次比较。
由Stirling公式可知，log≈(n!)≈nlog₂n一1．44n+O(log₂n)，所以基于关键字比较的分类时间的下界是D(nlog≈n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。

转载请注明原文地址:https://kaotiyun.com/show/QdCi777K

本试题收录于：计算机408题库学硕统考专业分类