你可能感興趣的試題

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

A.不能，因為它不可以用分、治、合三個步驟完成計算
B.不能，因為它不滿足分治法的第四個適應(yīng)條件（子問題是相互獨(dú)立的，也就是沒有重復(fù)子問題）
C.能，因為它滿足分治法的四個適應(yīng)條件
D.能，因為它可以用分、治、合三個步驟完成計算