【正文】 是 0。如果存在一個自然數 n0和一個正常數 c，使得 n≥n0 ， f(n)≤cg(n) 則稱 f(n)=O(g(n))， n0稱為閾值 。 ④表示時間復雜性的常用函數有： 常數： 1 運行時間為恒定值，和輸入無關。漸近運行時間通常稱為時間復雜性。 55 ① 漸近運行時間 去除表示算法運行時間函數的低價項和首項系數（常數）。因為當很大時低階項便顯得不太重要。在簡化過程中，僅考慮公式中的最高次項。 54 為了簡化對算法過程的分析，常常會忽略算法中每條語句的真實代價，而用常量 ci表示。 例某一算法運行時間為 2n3 ，當 n變得很大時，常數 2將不起作用。 ③算法應獨立于機器，無論科技如何進步，對算法運行時間的評估始終成立。理由如下： ①算法分析通常是將解決同一問題的各種算法之間進行相互比較，執(zhí)行時間是相對的，而不是絕對的。 執(zhí)行算法 BottomUpSort的最大比較次數 nlog2nn+1 執(zhí)行算法 SelectionSort的最大比較次數 n(n1)/2 假設一次比較所需的時間為 106秒，當數據個數 n分別為 27 =128 和 220 =1048576時，二個算法執(zhí)行所耗費的時間上限如下表所示： n SelectionSort BottomUpSort 27 106*128(1281)/2 ≈ 106*(128*7128+1) ≈ 220 106* 220 *(2201)/2≈ 106*(220*20 220+1) ≈ 20秒 53 ㈠ 概述 稱“一個算法 A對于輸入 x要用 y秒來運行”是沒有意義的，也是沒有必要的。 52 時間復雜性 在計算復雜性領域中，主要是研究一個算法所需要的時間和空間。 12?jnjn250 最多比較次數 ( k=log2n) ))211(( kkn ???)211( knnk ???knnnk2???1l o g 2 ??? nnn? ? ?????????? ??? kjjkjjjnnn11 2122????kjjnkn1 2151 觀察結論 （ Page 11) 用算法 BottomUpSort對 n個元素進行排序，當 n為 2的整數冪時，比較次數在(nlog2n)/2 到 nlog2nn+1 之間。 49 最少比較次數（ k=log2n） ④ 在第 j次迭代中， 個段（段長 =2j1）元素序列被合并成 個段（段長 =2j），段內有序。 ③在第 3次迭代中， n/4個段（段長 =4）元素序列被合并成 n/8個段（段長 =8），段內有序。 ②在第 2次迭代中， n/2個段（段長 =2）元素序列被合并成 n/4個段（段長 =4），段內有序。 ①在第 1次迭代中，共執(zhí)行了 n/2 次比較。 1 2 3 4 5 6 7 8 9 10 11 48 ㈣ 自底向上合并排序算法分析 假設數組元素個數 n為 2的冪（ n=2k=2log n），外部循環(huán)次數為 k=log2n。 出循環(huán)后， i+s=0+8＜ n=11成立，執(zhí)行 MERGE(A,1,8,n)。 出循環(huán)后， i+s=8+4＜ n=11不成立，因此不再合并，最后一個序列長度為 3。 出循環(huán)后， i+s=8+2＜ n=11成立，執(zhí)行 MERGE(A,9,10,n)，最后一個序列長度為 3。 出循環(huán)后， i+s=10+1=11＜ n=11不成立，因此不再合并，最后一個序列長度為 1（或稱剩下的元素個數）。如果剩余元素數目大于 s，就要將最后一個長度為 s的子序列和剩余元素進行一次合并排序，此時二個子序列合并后的長度小于 t=2s。 42 算法 BottomUpSort（ Page 10） 輸入： n個元素的數組 A[1..n] 輸出：按升序排列的數組 A[1..n] 1. t←1 2. while tn 3. s←t : t←2s : i←0 //i表示要處理數據的起始地址 (簡稱位移 ) 4. while i+t≤n 5. Merge(A,i+1,i+s,i+t) //Merge(A,p,q,r) 6. i←i+t //i表示要處理數據的起始地址 (簡稱位移 ) 7. end while 8. if i+sn then Merge(A,i+1,i+s,n) 9. end while //起始地址 +被合并前子序列長度＜ n，則合并。 jn22 4 5 9 1 4 6 7 1 2 4 4 5 6 7 9 2 4 5 9 1 4 7 1 2 4 4 5 7 9 ④ 總的迭代次數 k的值范圍為： 2k1＜ n≤ 2k 。 ?若 1≤r≤ 2j1(j=3,r=14)，則讓它們進入下一次合并（局部已有序）。 4n22n2 4 5 9 4 9 2 5 1 7 4 6 1 4 6 7 2 4 5 9 4 9 2 5 1 7 4 1 4 7 41 剩余元素為 7個 ③ 第 j次迭代（假設 j=3） 生成元素個數為 2j個的排序序列，該序列共有 個。若剩余 1或 2個，則讓它進入下一輪合并。若剩余 1個元素，則讓它進入下一輪合并。 觀察結論 （ Page 7） 執(zhí)行算法 Merge，將個數分別為 n1和 n2的非空數組合并成一個為 n= n1+n2的排序數組，元素的賦值次數恰好是 2n。設n1≤n2 ，元素的比較次數在 n1和 n1之間。所以，算法 Merge的最少比較次數是n1，最大比較次數為 n1。 另一方面，比較次數最多為 n1= n1+n21次。 1. ment:B[p..r]為輔助數組 //或 B[1..m] 2. s←p : t←q+1 : k←p //s和 t分別指向數組 A二個子數組元素 3. while (s≤q) and (t≤r) //k指向數組 B當前空白元素位置 4. if A[s]≤A[t] then B[k]←A[s] : s←s+1 5. else B[k]←A[t] : t←t+1 6. end if 7. k←k+1 //指向數組 B下一個空白位置 8. end while 9. if s=q+1 then B[k..r]←A[t..r] //子數組 A[p..q]元素已處理完 10. else B[k..r]←A[s..q] //否則 t=r+1,子數組 A[q+1..r]已處理完。 34 過程 Merge(A[1..m],p,q,r)（ Page 67） 輸入：數組 A[1..m]和它的三個索引 p,q,r（ 1≤p≤q＜ r≤m），二個子數組 A[p..q]和 A[q+1..r]各自按升序排列。 ①使用二個指針 s和 t，初始化時 s=p、 t=q+1， s和 t各自指向 A[p]和 A[q+1]，空數組 B[p..r]用作暫存器； ②每一次比較元素 A[s]和 A[t]，將小的元素添加到 B中。然后 i增 1，排序過程直至 i=n結束。然后 i增 1，排序過程直至 i=n1結束。 元素賦值次數等于元素比較次數加上 n1，即 2(n1)至 n(n1)/2+(n1)之間。如下所示： 21)n( n1)(n...21 ????? 因為每個元素 A[i] (2≤i≤n)都和子序列 A[1..i1]中的每個元素比較，這一結果與算法 SelectionSort相一致。 ①當元素已按升序排列時，元素比較次數最小，僅為 n1，每個元素 A[i]（ 2≤i≤n）只和 A[i1]比較。 28 過程 Insertion（參見 Page 89） 輸入： A[1..i1]已按升序排列 輸出： A[1..i] 按升序排列 0. procedure Insertion(i) 1. x←A [i] 2. j←i 1 3. while (j0) and (A[j]x) 4. A[j+1]←A[j] 5. j←j 1 6. end while 7. A[j+1]←x 8. end procedure 29 ㈡ 插入排序算法 設 A[1..n]為 n個元素的數組，插入排序算法描述如下： ①從子數組 A[1]開始，單個數可認為有序； ②接下來，將 A[2]插入到 A[1]的前面或后面，使得A[1..2]有序； ③然后，再將 A[3]插入到 A[1..2]中，使得 A[1..3]有序； ④直到 A[n]插入到 A[1..n1]，使得 A[1..n]有序。 依次掃描序號從 j=i1到 j=1的元素，將 x和 A[j]比較。 A[1..i1]已按升序排列。 觀察結論 (Page 8) 執(zhí)行算法 SelectionSort所需的元素比較次數為 n(n1)/2，元素的賦值次數界于 0與 3(n1)之間。 0. procedure Selection(i) 1. k←i 2. for j←i+1 to n 3. if A[j]A[k] then k←j 4. end for 5. if k≠i then 交換 A[i]和 A[k] 6. end procedure 24 ㈡ 選擇排序算法 設 A[1..n]為 n個元素的數組，選擇排序算法如下： ①首先在 n個元素中找到最小元素，將其存放在 A[1]中； ②然后在剩下的 n1個元素中找到最小元素，將其存放在A[2]中； ③重復上述過程，直至在二個元素 A[n1]和 A[n]中找到較小元素，將其存放在 A[n1]中。編寫一函數，作用為：從 A[i..n] 中選擇一個最小的數 A[k]（ i＜ k≤n） ，將 A[i]和 A[k]互換（若 k＝ i，無需交換）。 ? 因此，解決同一個問題，算法不同，計算的工作量也不同，所需的計算時間隨之不同，即算法的時間復雜性不同。由于決策樹的高度為 ?Log2n? ，所以二分搜索法的最大比較次數為 ?Log2n? +1。 序列： 1 4 5 7 8 9