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