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