以比较为基础的排序算法在最坏情况下的计算时间下界为(55)。A．O(n)B．O(n2)C．O(logn)D．O(nlogn)
题目
以比较为基础的排序算法在最坏情况下的计算时间下界为(55)。
A．O(n)
B．O(n2)
C．O(logn)
D．O(nlogn)
相似考题
更多“以比较为基础的排序算法在最坏情况下的计算时间下界为(55)。A.O(n)B.O(n2)C.O(logn)D.O(nlogn) ”相关问题
-
第1题：
以关键字比较为基础的排序算法，在最坏情况下的计算时间下界为(65)。
A．O(2n)
B．O(n2)
C．O(logn)
D．O(nlogn)
正确答案：C
解析：利用二元树可以证明对任何以关键字比较为基础的排序算法，最坏情况的计算时间下界都为O(logn)，如归并排序算法。 -
第2题：
快速排序方法(Quick Sort)的时间复杂度为(61)。
A．O(n2)
B．O(nlogn)
C．O(n)
D．O(logn)
正确答案：B
解析：对长度为n的序列进行快速排序，设所需时间为T(n)，则可知T(n)=T(k-1)+T(n-k)+cn。cn表示对n个记录进行一趟快速排序所需的时间。递归即可得出快速排序方法(QuickSort)的时间复杂度为O(nlogn)。 -
第3题：
【单选题】直接插入排序在最好情况下的时间复杂度为（)。
A．O(logn)
B．O(n)
C．O(nlogn)
D．O(n2)
O(n) -
第4题：
以比较为基础的排序算法在最坏情况下的计算时间下界为(59)。
A．O(n)
B．O(n2)
C．O(logn)
D．O(nlogn)
正确答案：D
解析：利用二叉树可以证明对任何以关键字比较为基础的排序算法的最坏情况下的时间复杂度都为O(nlogn)，如归并排序等。 -
第5题：
二路归并排序算法的时间复杂度为（）
A．O(logn)
B．O(nlogn)
C．O(n)
D．O(1)
O(nlog 2 n)