問答題

【簡答題】
設函數(shù)f1、f2和f3的處理時間分別為O（n）、O（n²）和O（1），分析下列流程的時間復雜性：

答案：

你可能感興趣的試題

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

答案：

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

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

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