以比较为基础的排序算法在最坏情况下的计算时间下界为(55)。A.O(n)B.O(n2)C.O(logn)D.O(nlogn)

Question

以比较为基础的排序算法在最坏情况下的计算时间下界为(55)。

A．O(n)

B．O(n2)

C．O(logn)

D．O(nlogn)

Answer 1

正确答案：D
解析：此问题考查以比较为基础的排序算法的时间复杂度分析，利用二元树可以证明对任何以关键字比较为基础的排序算法，最坏情况的计算时间下界都为O(nlogn)，如归并排序算法。