单项选择题快速排序和归并排序是常用的排序算法,也都是采用分治法解决的问题。快速排序的时间复杂性为O(n2),而归并排序的时间复杂性为O(nlogn),究其原因,下面的解释哪个正确?()
A.这是因为归并排序把问题划分为子问题时的时间复杂性是O(1),而快速排序划分为子问题是使用partition()函数,其时间复杂性是O(n)
B.因为归并排序把问题划分为两个子问题时其规模大致相等,是原来规模的n/2,而快速排序划分为子问题是使用partition()函数,划分为子问题时不能保证二个子问题的规模大致相同,在极端状况下,每次都只划分为1个子问题,其规模为原问题规模n-1,因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n)
C.因为快速排序将问题划分为子问题的个数比归并排序要多
D.归并排序的分和合的时间复杂性之和低于快速排序的分和合的时间复杂性之和