單項(xiàng)選擇題

?快速排序和歸并排序是常用的排序算法,也都是采用分治法解決的問題??焖倥判虻臅r間復(fù)雜性為O(n2),而歸并排序的時間復(fù)雜性為O(nlogn),究其原因,下面的解釋哪個正確?()

A.這是因?yàn)闅w并排序把問題劃分為子問題時的時間復(fù)雜性是O(1),而快速排序劃分為子問題是使用partition()函數(shù),其時間復(fù)雜性是O(n)
B.因?yàn)闅w并排序把問題劃分為兩個子問題時其規(guī)模大致相等,是原來規(guī)模的n/2,而快速排序劃分為子問題是使用partition()函數(shù),劃分為子問題時不能保證二個子問題的規(guī)模大致相同,在極端狀況下,每次都只劃分為1個子問題,其規(guī)模為原問題規(guī)模n-1,因此快速排序在極端狀況下的時間復(fù)雜性的遞歸定義為T(n)=T(n-1)+O(n)
C.因?yàn)榭焖倥判驅(qū)栴}劃分為子問題的個數(shù)比歸并排序要多
D.歸并排序的分和合的時間復(fù)雜性之和低于快速排序的分和合的時間復(fù)雜性之和

題目列表

你可能感興趣的試題

微信掃碼免費(fèi)搜題