在快速排序中，以下描述不正确的是（ ）。
A: 在快速排序，最好时间复杂性和平均时间复杂性均为Ο(nlogn)
B: 若精心挑选一个划分元，每次经过Partition算法后，分成两个子问题，从而使得其最坏时间复杂性为Ο(nlogn)
C: 若随机挑选一个划分元，每次经过RandomizedPartition算法后，分成两个期望均长的子问题，从而使得其期望时间复杂性为Ο(nlogn)
D: 不管是精心挑选还是随机挑选划分元，快速排序的最坏时间复杂性均为Ο(n2)
A: 在快速排序，最好时间复杂性和平均时间复杂性均为Ο(nlogn)
B: 若精心挑选一个划分元，每次经过Partition算法后，分成两个子问题，从而使得其最坏时间复杂性为Ο(nlogn)
C: 若随机挑选一个划分元，每次经过RandomizedPartition算法后，分成两个期望均长的子问题，从而使得其期望时间复杂性为Ο(nlogn)
D: 不管是精心挑选还是随机挑选划分元，快速排序的最坏时间复杂性均为Ο(n2)
举一反三
- 快速排序和归并排序是常用的排序算法，也都是采用分治法解决的问题。快速排序的时间复杂性为O(n2), 而归并排序的时间复杂性为O(nlogn), 究其原因，下面的解释你认为哪个正确？（ ） A: 这是因为归并排序把问题划分为子问题时的时间复杂性低，而快速排序划分为子问题是使用partition()函数，划分为子问题的时间复杂性高。 B: 归并排序的分和合的时间复杂性之和低于快速排序的分和合的时间复杂性之和。 C: 因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n)。 D: 以上都不正确。
- 二分搜索算法在最坏情况下的时间复杂性是快速排序算法在平均情况下的时间复杂性是
- 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。 （ ）
- 快速排序在平均情况下的时间复杂性为________,在最坏情况下的时间复杂性为____。
- 【多选题】关于快速排序分治算法时间复杂度描述正确的是() A. 快速排序分治算法最好情况下的时间复杂度为O(nlogn). B. 快速排序分治算法最坏情况下的时间复杂度为O(n 2 ). C. 快速排序分治算法平均情况下的时间复杂度为O(n 2 ). D. 二快速排序分治算法平均情况下的时间复杂度为O(nlogn).