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

Question

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

A．O(n)

B．O(n2)

C．O(logn)

D．O(nlogn)

Answer 1

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