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

admin2017-11-14  31

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

选项 A、O(nlog2n)
B、O(log2n)
C、O(n)
D、O(n2)

答案A

解析 此题考查的知识点是各类排序的效率。理论上可以证明,对于基于关键字之间比较的分类,无论用什么方法都至少需要进行log2(n!)次比较。由Stirling公式可知,log2(n!)≈nlog2n—1.44n+O(log2n)。所以基于关键字比较的分类时间的下界是O(nlog2n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。
转载请注明原文地址:https://kaotiyun.com/show/C3Ri777K
0

最新回复(0)