【正文】 一個問題可能會有多種算法可供選擇，選擇的主要標準首先是算法的 正確性和可靠性，簡單性和易理解性 。 8 ? 算法是問題求解過程的精確描述。 “計算復雜性”是研究可解類問題的效率。 6 7 歷史背景 20世紀早期，能否用一種有效的過程（算法）來求解問題，受到廣泛的關注。 5 算法分析（ Algorithm Analysis） 算法分析研究的目標為：算法一旦轉換成某種語言的程序，該程序在計算機上運行，需要多少時間和存儲空間才能完成解題方案。1 第 1章 算法分析基本概念 2022年 2月 23日 2 引言 歷史背景 算法復雜性 時間復雜性 空間復雜性 排序 選擇排序 插入排序 自底向上合并排序 冒泡排序 希爾排序 快速排序 3 引言 計算機科學就是 算法研究 4 算法（ Algorithm） 解題方案的準確完整的描述，是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。 確定一個程序的運行效率，既可使用數(shù)學分析方法，也可使用實驗測試方法，可以在理論和實踐二個方面作出評估。人們的注意力是放在問題的可解和不可解的分類上。效率是用解決問題所需的時間和空間來描述的。一個算法由有限條可完成或機械地執(zhí)行的，有結果指令組成。其次是算法所需要的 存儲空間少和執(zhí)行更快 等。 ? 計算機的資源。 ? 關于算法的復雜性，有兩個問題要弄清楚： – 用怎樣的一個量表達一個算法的復雜性； – 對于一個對定的一個算法，怎樣具體計算它的復雜性 11 算法復雜性 ? 問題：已知不重復且已經(jīng)按從小到大排好的 n個整數(shù)的數(shù)組 A[1..n]。 1. j←1 2. while (jn) and (x≠A[j]) 3. j←j+1 4. end while 5. if x=A[j] then return j else return 0 14 ㈡ 順序搜索法分析 最少比較次數(shù)為 1，最多比較次數(shù)為 n 。類似地，如果 xA[mid]，只需在A[low..mid1]中搜索 x。 1. low←1 : high←n : j←0 //j=0表示未找到 2. while (low≤high) and (j＝ 0) 3. mid← ?(low+high)/2? //? ?表示向下 取整 (Page 45) 4. if x＝ A[mid] then j←mid 5. else 6. if x＜ A[mid] then high←mid 1 7. else low←mid+1 //x＞ A[mid] 8. end if 9. end if 10. end while 11. return j 16 1 4 5 7 8 9 10 12 15 22 23 27 32 35 A[1..14] = A[8..14] = 12 15 22 A[8..10] = ① 要搜索元素 x=22。 ④ 留在序列中僅剩一個項目 A[10]=22，最后找到 x=A[10]，搜索成功完畢（若 x≠A[10]，則 low≤high條件不成立，出循環(huán)）。 若 n是奇數(shù)， A[mid+1..n]共有 (n1)/2個元素。 序列： 1 4 5 7 8 9 10 12 15 22 23 27 32 35 ?log214?+1=4 21 ?比較次數(shù)是指元素比較次數(shù)，所以在 while語句中的非元素比較次數(shù)，通常不予計入 ； ?確切講，比較次數(shù)是指布爾表達式“ x=A[mid]”的執(zhí)行次數(shù)； ?由于 ifthenelse嵌套使用，實際元素比較最大次數(shù)應為循環(huán)（迭代）次數(shù)的 2倍，即 2( ?Log2n?+1)。 ? 因此，解決同一個問題，算法不同，計算的工作量也不同，所需的計算時間隨之不同，即算法的時間復雜性不同。 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個元素的數(shù)組，選擇排序算法如下： ①首先在 n個元素中找到最小元素，將其存放在 A[1]中； ②然后在剩下的 n1個元素中找到最小元素，將其存放在A[2]中； ③重復上述過程，直至在二個元素 A[n1]和 A[n]中找到較小元素，將其存放在 A[n1]中。 A[1..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個元素的數(shù)組，插入排序算法描述如下： ①從子數(shù)組 A[1]開始，單個數(shù)可認為有序； ②接下來，將 A[2]插入到 A[1]的前面或后面，使得A[1..2]有序； ③然后，再將 A[3]插入到 A[1..2]中，使得 A[1..3]有序； ④直到 A[n]插入到 A[1..n1]，使得 A[1..n]有序。如下所示： 21)n( n1)(n...21 ????? 因為每個元素 A[i] (2≤i≤n)都和子序列 A[1..i1]中的每個元素比較，這一結果與算法 SelectionSort相一致。然后 i增 1，排序過程直至 i=n1結束。 ①使用二個指針 s和 t，初始化時 s=p、 t=q+1， s和 t各自指向 A[p]和 A[q+1]，空數(shù)組 B[p..r]用作暫存器； ②每一次比較元素 A[s]和 A[t]，將小的元素添加到 B中。 1. ment:B[p..r]為輔助數(shù)組 //或 B[1..m] 2. s←p : t←q+1 : k←p //s和 t分別指向數(shù)組 A二個子數(shù)組元素 3. while (s≤q) and (t≤r) //k指向數(shù)組 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 //指向數(shù)組 B下一個空白位置 8. end while 9. if s=q+1 then B[k..r]←A[t..r] //子數(shù)組 A[p..q]元素已處理完 10. else B[k..r]←A[s..q] //否則 t=r+1,子數(shù)組 A[q+1..r]已處理完。所以，算法 Merge的最少比較次數(shù)是n1，最大比較次數(shù)為 n1。 觀察結論 （ Page 7） 執(zhí)行算法 Merge，將個數(shù)分別為 n1和 n2的非空數(shù)組合并成一個為 n= n1+n2的排序數(shù)組，元素的賦值次數(shù)恰好是 2n。若剩余 1或 2個，則讓它進入下一輪合并。 ?若 1≤r≤ 2j1(j=3,r=14)，則讓它們進入下一次合并（局部已有序）。 42 算法 BottomUpSort（ Page 10） 輸入： n個元素的數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. t←1 2. while tn 3. s←t : t←2s : i←0 //i表示要處理數(shù)據(jù)的起始地址 (簡稱位移 ) 4. while i+t≤n 5. Merge(A,i+1,i+s,i+t) //Merge(A,p,q,r) 6. i←i+t //i表示要處理數(shù)據(jù)的起始地址 (簡稱位移 ) 7. end while 8. if i+sn then Merge(A,i+1,i+s,n) 9. end while //起始地址 +被合并前子序列長度＜ n，則合并。 出循環(huán)后， i+s=10+1=11＜ n=11不成立，因此不再合并，最后一個序列長度為 1（或稱剩下的元素個數(shù)）。 出循環(huán)后， i+s=8+4＜ n=11不成立，因此不再合并，最后一個序列長度為 3。 1 2 3 4 5 6 7 8 9 10 11 48 ㈣ 自底向上合并排序算法分析 假設數(shù)組元素個數(shù) n為 2的冪（ n=2k=2log n），外部循環(huán)次數(shù)為 k=log2n。 ②在第 2次迭代中， n/2個段（段長 =2）元素序列被合并成 n/4個段（段長 =4），段內(nèi)有序。 49 最少比較次數(shù)（ k=log2n） ④ 在第 j次迭代中， 個段（段長 =2j1）元素序列被合并成 個段（段長 =2j），段內(nèi)有序。 52 時間復雜性 在計算復雜性領域中，主要是研究一個算法所需要的時間和空間。理由如下： ①算法分析通常是將解決同一問題的各種算法之間進行相互比較，執(zhí)行時間是相對的，而不是絕對的。 例某一算法運行時間為 2n3 ，當 n變得很大時，常數(shù) 2將不起作用。在簡化過程中，僅考慮公式中的最高次項。 55 ① 漸近運行時間 去除表示算法運行時間函數(shù)的低價項和首項系數(shù)（常數(shù)）。 ④表示時間復雜性的常用函數(shù)有： 常數(shù)： 1 運行時間為恒定值，和輸入無關。 正常數(shù)，可以是 0。 解： 當 n≥4，有 n2≤ 2n 故當 n≥4，有 f(n) = 6*2n+n2 ≤ 6*2n + 2n = 7*2n 令 g(n)= 2n ，因為當 n≥4時有 f(n)≤7g(n) 所以 f(n)=O(g(n))=O(2n) ?O符號提供了運行時間的上界； ?算法 InsertionSort執(zhí)行的比較次數(shù)最多為 2（ n(n1)/2 =）， c為某個適當選擇的常數(shù)，則稱該算法的運行時間是