第1章漸增型算法徐子珊

第1章集腋成裘漸增型算法1.1算法設(shè)計與分析1．什么是算法算法是解決一個計算問題的一系列計算步驟有序、合理的排列。對一個具體問題（有確定的輸入數(shù)據(jù)）依次執(zhí)行一個正確的算法中的各操作步驟，最終將得到該問題的解（正確的輸出數(shù)據(jù)）。2．算法分析基本概念算法運行所需要的計算機(jī)資源的量稱為算法的復(fù)雜性。計算算法運行所需資源量的過程稱為算法復(fù)雜性分析，簡稱為算法分析。理論上，算法分析既要計算算法的時間復(fù)雜性，也要計算它的空間復(fù)雜性。本書中除非特別說明，所說的算法分析，僅局限于對算法的時間復(fù)雜性分析。隨機(jī)訪問計算機(jī)RAMRAM只用一個處理機(jī)，卻有無限量的隨機(jī)存儲器。它的有限個基本操作——算術(shù)運算、邏輯運算和數(shù)據(jù)的移動（比如對變量的賦值）均在有限固定時間內(nèi)完成，假定所有這些基本操作都消耗一個時間單位。算法在RAM上運行所需的時間，顯然就是執(zhí)行基本操作的次數(shù)。算法運行時間的3種情形對固定的輸入規(guī)模，使運算時間最長的輸入所消耗的運行時間稱為算法的最壞情形時間。對固定的輸入規(guī)模，使運行時間最短的輸入所消耗的時間，稱為最好情形時間。假定固定的輸入規(guī)模為n，所有不同輸入構(gòu)成的集合為Dn，對問題的每一個輸入為IDn，若已知該輸入發(fā)生的概率為P(I)，對應(yīng)的運行時間為T(I)，運行時間的數(shù)學(xué)期望值稱為算法的平均情形時間。3．實例在線性表A中查找。（a）查找值為x=1的元素，從A[1]起依次要進(jìn)行5次檢測，第一次找到值為1的元素。（b）查找值為x=11的元素，從A[1]起依次檢測完所有元素（進(jìn)行10次檢測），沒有找到值為11的元素——最壞情形。（c）查找值為x=3的元素，從A[1]起僅進(jìn)行一次檢測就找到值為3的元素——最好情形。4．算法的漸進(jìn)運行時間當(dāng)n時，評估T（n）趨于無窮大的快慢來分析算法的時間復(fù)雜性。我們往往用幾個函數(shù)?（n）：冪函數(shù)nk（k為正整數(shù)）、對數(shù)冪函數(shù)lgkn（k為正整數(shù)，底數(shù)為2）和指數(shù)函數(shù)an（a為大于1的常數(shù)）作為“標(biāo)準(zhǔn)”，研究極限：若λ=非零常數(shù)，則稱?（n）是T（n）的漸近表達(dá)式，或稱T（n）漸近等于?（n），記為T（n）=Θ（?（n）），這個記號稱為算法運行時間的漸近Θ-記號，簡稱為Θ-記號。5．有效算法如果兩個算法運行時間的漸近表達(dá)式相同，則將它們視為具有相同時間復(fù)雜度的算法。顯然，漸近時間為對數(shù)冪的算法優(yōu)于漸近時間為冪函數(shù)的算法，而漸近時間為冪函數(shù)的算法則優(yōu)于漸近時間為指數(shù)函數(shù)的算法。我們把漸近時間為冪函數(shù)的算法稱為是具有多項式時間的算法，漸近時間不超過多項式的算法則稱其為有效的算法。6．漸增型算法漸增型算法有一個共同的特征：構(gòu)成算法的主體是一個循環(huán)結(jié)構(gòu)，它逐步將部分解擴(kuò)張成一個完整解。該循環(huán)將遵循一個始終不變的原則：每次重復(fù)之初，總維持著問題的一個部分解。我們將此特征稱為算法的循環(huán)不變量。1.2插入排序算法1．問題的理解與描述排序問題的形式化表示為：輸入：一組數(shù)<a1,a2,...,an>。輸出：輸入的一個排列（重排）<a'1,a'2,...,a'n>，滿足a'1a'2,...,a'n。2．算法的偽代碼描述INSERTION-SORT（A）1forj←2tolength[A]2 dokey←A[j]3 將A[j]插入到排好序的序列A[1…j-1]中。4 i←j-15 whilei>0andA[i]>key6 doA[i+1]←A[i]7 i←i-18 A[i+1]←keyINSERTION-SORT在A=<7,4,6,8,3,5>上的操作數(shù)組的下標(biāo)表示在各方格的上方，存儲在數(shù)組中的數(shù)值表示在各方格內(nèi)。（a）～（e）第1～8行的for循環(huán)的各次重復(fù)。每次重復(fù)中，黑色方格放的是鍵A[j]，它在第5行中逐一與其左邊灰色方格內(nèi)的元素比較?；疑募^指示處在第6行中被右移一格的元素，黑色箭頭則指示出鍵在第8行移動到的位置。（f）最終排好序的數(shù)組。3．算法的正確性循環(huán)不變量第1～8行的for循環(huán)的每次重復(fù)之初，子序列A[1…j-1]由原來A[1…j-1]中的元素組成，且已排好序。

4．算法的運行時間假定序列A含有n個元素，對INSERTION-SORT而言，最壞情形是序列A初始狀態(tài)是降序排列。在此情形下，對第1～8行的for循環(huán)的n-1次重復(fù)的每一次，內(nèi)嵌的第5～7行的while循環(huán)將分別重復(fù)1，2，…，n-1次。所以，第6～7行的操作將重復(fù)進(jìn)行1+2+…+n-1=n（n-1）/2次。于是，該算法的最壞情形時間用Θ-記號表示為Θ(n2)。1.3兩個有序序列的合并算法1．問題的理解與描述將兩個有序序列合并為一個有序序列問題的形式化表示為：輸入：序列A[p…r]。其中，子序列A[p...q]和A[q+1...r]是有序的。輸出：A[p...r]所有元素的重排，使之有序。2．算法的偽代碼描述MERGE(A,p,q,r)1n1←q-p+12n2←r-q3創(chuàng)建數(shù)組L[1…n1]和R[1…n2]4fori←1ton15 doL[i]←A[p+i-1]6forj←1ton27 doR[j]←A[q+j]8i←19j←110

k←p11whilei

n1andjn212 doifL[i]R[j]13 thenA[k]←L[i]14 i←i+115 elseA[k]←R[j]16 j←j+117 k←k+118ifi<n119 then將L[i...n1]復(fù)制到A[k...r]20ifj<n221 then將R[j...n2]復(fù)制到A[k...r]對序列A[9..16]=<2,4,5,7,1,2,3,6>運行MERGE過程使用兩個輔助數(shù)組L和R進(jìn)行合并操作。在復(fù)制后，數(shù)組L包含<2,4,5,7>，數(shù)組R包含<1,2,3,6>。A中深灰色的位置包含最終值，L和R中淺灰色位置包含的值尚未復(fù)制回A中。A的淺灰色位置是將被覆蓋的，而L和R中深灰色位置包含的是已經(jīng)被復(fù)制回A的值。(a)～(g)是第12～17行的while循環(huán)每次重復(fù)之初的A、L、R及其下標(biāo)k、i、j。(h)是執(zhí)行了第18～21將L中剩余的元素復(fù)制到A[k...r]中。此時，子數(shù)組A[9…16]已經(jīng)排好序。3．算法的正確性循環(huán)不變量：在第12～17行的while循環(huán)的每次重復(fù)之初，子數(shù)組A[p…k-1]包含L[1…n1]和R[1…n2]中的k-p個最小的元素，并排好序。此外，L[i]和R[j]分別是各自數(shù)組中尚未復(fù)制回數(shù)組A的元素中的最小者。可利用此循環(huán)不變量來證明合并算法MERGE是正確的。1.4序列的劃分1．問題的理解與描述序列的劃分問題描述如下：輸入：序列A[p…r]。輸出：下標(biāo)q（p

q

r），原序列A[p…r]的一個重排：使得A[p…q]中的元素值不超過A[q](=原A[r]的值)，而A[q+1...r]中的元素值均大于A[q]。2．算法的偽代碼描述PARTITION(A,p,r)1x←A[r]2i←p-13forj←ptor-14 doifA[j]

x5 theni←i+16 exchangeA[i]?A[j]7exchangeA[i+1]?A[r]8returni+1對一個樣本序列的劃分操作（a）初始的序列和變量設(shè)置。沒有任何元素進(jìn)入上述兩部分。（b）～（h）表示第3～6行的for循環(huán)的每一次重復(fù)。黑色雙向箭頭表示第6行的元素交換操作。（i）表示上述循環(huán)終止后第7行執(zhí)行的元素交換操作。3．算法的正確性循環(huán)不變量：在第3～6行的for循環(huán)的每次重復(fù)之初，對每一個數(shù)組下標(biāo)k，若p