【正文】 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)。 n=11,mid= ?(11+1)/2? =6,剩余元素 A[7..11]，共計 5個 ( ?11/2? )。 若 n是奇數(shù)， A[mid+1..n]共有 (n1)/2個元素。為了計算最大比較次數(shù)，不失一般性，可假定 x≥A[high] 。 ④ 留在序列中僅剩一個項目 A[10]=22，最后找到 x=A[10]，搜索成功完畢（若 x≠A[10]，則 low≤high條件不成立，出循環(huán)）。 ② 在剩余元素 A[8..14]中搜索 x=22， A[?(8+14)/2?]=A[11]=23，由于 xA[11]，可以把 A[11..14]掉棄。 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。 15 算法 BinarySearch（ Page 4） 輸入： n個元素的數(shù)組 A[1..n]（按升序排列）和元素 x。類似地，如果 xA[mid]，只需在A[low..mid1]中搜索 x。假定 xA[mid]，如果 x在A中，則它必定是 A[mid+1]， A[mid+2]， … ， A[high] 中的一個，接下來只需在 A[mid+1..high]中搜索 x。 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 。按照該方法，或者掃到 A的第 i個分量時發(fā)現(xiàn)滿足 A[j]=x，或者掃到 A的最后一個分量，經(jīng)檢測仍不滿足 A[j]=x 12 算法復雜性 13 出循環(huán)分析： ① x=A[j]，此時 jn； ② j等于 n，但 A[n]與 x尚未比較（或相等或不相等）。 ? 關于算法的復雜性，有兩個問題要弄清楚： – 用怎樣的一個量表達一個算法的復雜性； – 對于一個對定的一個算法，怎樣具體計算它的復雜性 11 算法復雜性 ? 問題：已知不重復且已經(jīng)按從小到大排好的 n個整數(shù)的數(shù)組 A[1..n]。因而算法的復雜性有時間復雜性和空間復雜性之分。 ? 計算機的資源。一個算法的復雜性的高低體現(xiàn)在運行該算法所需要的計算機資源的多少。其次是算法所需要的 存儲空間少和執(zhí)行更快 等。計算機按算法指令所描述的順序使得算法的指令能在有限的步驟內(nèi)終止，或終止于給出問題的解，或終止于指出問題對此輸入數(shù)據(jù)無解。一個算法由有限條可完成或機械地執(zhí)行的，有結果指令組成。計算機程序要對問題的每個對象和處理規(guī)則給出正確詳盡的描述，其中程序的 數(shù)據(jù)結構 和 變量 用來描述問題的對象， 程序結構 ， 函數(shù) 和 語句 用來描述問題的算法、 算法 和 數(shù)據(jù)結構是程序的兩個重要方面。效率是用解決問題所需的時間和空間來描述的。 數(shù)字計算機出現(xiàn)以后，由于有限的資源，提出了盡可能少用資源的有效算法的需求，導致出現(xiàn)計算復雜性的新領域。人們的注意力是放在問題的可解和不可解的分類上。沒有輸出的算法毫無意義； – 可行性 ：算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。 確定一個程序的運行效率，既可使用數(shù)學分析方法，也可使用實驗測試方法，可以在理論和實踐二個方面作出評估。前者是推理實現(xiàn)，后者是操作實現(xiàn)； ② 算法不是程序，但算法是用程序或偽代碼來描述的。1 第 1章 算法分析基本概念 2022年 2月 23日 2 引言 歷史背景 算法復雜性 時間復雜性 空間復雜性 排序 選擇排序 插入排序 自底向上合并排序 冒泡排序 希爾排序 快速排序 3 引言 計算機科學就是 算法研究 4 算法（ Algorithm） 解題方案的準確完整的描述，是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。 ① 無論是解題思路還是編寫程序，都是在實施某種算法。 5 算法分析（ Algorithm Analysis） 算法分析研究的目標為：算法一旦轉換成某種語言的程序，該程序在計算機上運行，需要多少時間和存儲空間才能完成解題方案。 算法特征 ? 一個算法應具有以下五個重要的特征： – 有窮性 ：一個算法必須保證執(zhí)行有限點之后結束； – 確切性 ：算法的每一步驟須有確切的定義； – 輸入 ：一個算法有 0個或多個輸入，以刻畫運算對象的初始情況，這里 0個輸入是指算法本身定義了初始條件； – 輸出： 一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結果。 6 7 歷史背景 20世紀早期，能否用一種有效的過程（算法）來求解問題，受到廣泛的關注。 問題的可判定性和可解性的研究領域，稱為“可計算理論”。 “計算復雜性”是研究可解類問題的效率。 歷史背景 ? 要使計算機完成人們預定的工作，首先必須為如何完成預定的工作設計一個算法，然后再根據(jù)算法編寫程序。 8 ? 算法是問題求解過程的精確描述。指令正確地描述了要完成的任務和它們所執(zhí)行的順序。 ? 通常求解一個問題可能會有多種算法可供選擇，選擇的主要標準首先是算法的 正確性和可靠性，簡單性和易理解性 。 9 歷史背景 算法復雜性 ? 算法的復雜性是算法效率的質量，是評價算法優(yōu)劣的重要依據(jù)。所需的資源越多，該算法的復雜性越高；反之，所需的資源越低，該算法的復雜性越低。最重要的是 時間和空間 （即存儲器）資源。 10 ? 對于任意給定的問題，設計出復雜性盡可能低的算法是我們在設計算法過程中追求的一個重要目標責任制，另一方面，當給定的問題已經(jīng)有多種算法時，選擇其中之復雜性最低者，是我們在選用算法適應遵循的一個重要準則，因此，算法的復雜性分析對算法的設計或選用有著重要的指導意義和實用價值。對于給定的整數(shù) x，要求尋找一個下標，使得 A[j]=x，若找不到，則返回一個 0. ? 該問題的一個簡單算法是：從頭到尾掃描數(shù)組 A。 算法 LinearSearch（ Page 3） 輸入： n個元素的數(shù)組 A[1..n]和元素 x 輸出：如果 x=A[j]（ 1≤j≤n），則輸出 j，否則輸出 0。 ㈢二分搜索 令 A[low..high]為元素按升序排列的非空數(shù)組，數(shù) A[mid] 為中間元素。換句話說， A[low..mid]中的項目在后續(xù)比較中被掉棄了。由于重復進行二等分，導致了一個稱為二分搜索的有效策略。 輸出：如果 x=A[j]， 1≤j≤n，則輸出 j，否則輸出 0。首先將 x與 A的中間元素比較，A[?(1+14)/2?]=A[7]=10，由于 xA[7]，可以把 A[1..7]掉棄。 12 15 22 23 27 32 35 考慮搜索數(shù)組 1 7 14 8 11 14 8 9 10 17 A[10] = 22 ③ 在剩余元素 A[8..10]中搜索 x=22， A[?(8+10)/2?]=A[9]=15，由于 xA[9]，可以把 A[8..9]掉棄。 10 12 15 22 A[8..10] = 8 9 10 18 ㈣ 二分搜索法分析 假定每個三向比較 (ifthenelse)計為一次比較，顯然最小比較次數(shù)為 1，即搜索元素 x在序列中間位置。 ①第 2次迭代（循環(huán)）前數(shù)組 A中剩余元素 若 n是偶數(shù)， A[mid+1..n]共有 n/2個元素。 二種情況都有： A[mid+1..n] = ?n/2? = ?n/221? ② 第 3次迭代（循環(huán)）前數(shù)組 A中剩余元素 ? ?n/2? /2? = ?n/4? = ?n/22? = ?n/231 ? ③ 第 j次迭代（循環(huán)）前數(shù)組 A中剩余元素 ?n/2j1? ④ 不管找到與否，搜索 x的終止條件是余下元素僅僅為 1個，即 ?n/2j1? =1 n=10,mid= ?(10+1)/2? =5,剩余元素 A[6..10]，共計 5個 ( ?10/2? )。 19 當 ?n/2j1? =1， j為最大迭代次數(shù)（或稱最大循環(huán)次數(shù)、或稱最大比較次數(shù)） ?n/2j1?＝ 1 等價于 1≤n/2j1＜ 2 等價于 2j1≤n＜ 2j 等價于（取對數(shù)） j1≤Log2n＜ j 考慮 ?Log2n?≤Log2n＜ ?Log2n ?+1 因為 j是整數(shù)，故有 j1＝ ?Log2n ? 或 j＝ ?Log2n ?+1 二者均有 j＝ ?Log2n ?+1 20 107 5 2311 11 8 159 32 4 7 9 12 2210 27 3514 可將二分搜索法的執(zhí)行描述為決策樹，紅色的結點是與 x=22相比較的數(shù)字。