试题-快速排序的平均时间复杂度和最坏时间复杂度是?

题目

快速排序的平均时间复杂度和最坏时间复杂度是?

A.O(n^2), O(n^2)

B.O(n^2), O(nlgn)

C.O(nlgn) , O(nlgn)

D.O(nlgn) , O(n^2)

解答

正确答案是 D

当排序已经成为基本有序状态时，快速排序退化为O（n^2）

一般情况下，排序为指数复杂度。

C 8条回复评论

大葫芦

发表于 2018-10-13 15:55:45

毛大军

快排最差情况递归调用栈高度O(n)，平均情况递归调用栈高度O(logn),而不管哪种情况栈的每一层处理时间都是O(n),所以平均情况(最佳情况也是平均情况)的时间复杂度O(nlogn),最差情况的时间复杂度为O(n^2)

发表于 2018-10-13 15:55:30

小可爱

如果每一次寻找的基准基本都是中间值或者接近中间值的话，那么这就是最好的情况，此时，为nlogn，如果每次都是最大或最小的情况，那么此时为最差的情况，此时为n^2.

发表于 2018-10-13 15:55:17

窦先生

由于涉及到一个用来给数据分大小的值

所以很容易能理解，最好的情况就是，刚刚好取到中间值，然后两边大小相等，这样分下去的就是logN

又需要排序就是N*logN

最坏的情况，就是一串数字已经排序好，每次我都是取最大的值，然后始终都是得到一边有数字，另一边没有数字，这样加上排序，时间复杂度就是n^2

发表于 2018-10-13 15:55:04

王王王

随机快速排序的平均时间复杂度为O(nlogn)，当数组为逆序的时候，按从小到大的顺序进行排序时为最差情况，时间复杂度为O(n^2)

发表于 2018-10-13 15:54:48

人间喜剧

如果基准数恰是中位数，每次只需遍历当前数组长度的一半即可排好一个数，如果基准数是极值，就和冒泡，选择没啥区别了

发表于 2018-10-13 15:54:38

资深90后

平均复杂度相当于目标index在中间，类似二分法，最坏情况，每次从头到尾遍历整个数组

发表于 2018-10-13 15:54:29

皮皮鲁

平均就是数学期望，最坏的时候也就是在随机快速排序的partition过程的时候每次选取标志数的时候都大或者最小值，此时的时间复杂度为O(n^2)

发表于 2018-10-13 15:54:17