問答題

【簡答題】如果修改歸并排序算法，將數(shù)組分成1/3和2/3大小不等的兩部分，分別排序后再歸并，算法的最壞時間復(fù)雜度有什么變化？

答案：

設(shè)對n個元素排序的時間為T（n），對兩部分排序的時間分別為T（n/3）和，合并的時間為n-1，得到遞歸方程：

你可能感興趣的試題

【簡答題】用分割元素v將有n個元素的數(shù)組分割成元素大于v和小于v的兩部分，需要花多少時間（要講出道理）。

答案：至少需要對每個元素進行一次比較運算，運算時間是O（n）。

【簡答題】比較回溯法和分支限界法的搜索方式，哪種方法更適合找最優(yōu)解問題？

答案： 1）回溯法是在約束下帶跳躍的深度優(yōu)先搜索。
2）分枝限界是廣度優(yōu)先方式的按最小代價選擇擴展節(jié)點，以上界函數(shù)對活...