第 1 章 漸增型算法 徐子珊

1、第1章 集腋成裘 漸增型算法1.1 算法設(shè)計與分析 1什么是算法 算法是解決一個計算問題的一系列計算步驟有序、合理的排列。對一個具體問題（有確定的輸入數(shù)據(jù)）依次執(zhí)行一個正確的算法中的各操作步驟，最終將得到該問題的解（正確的輸出數(shù)據(jù)）。 2算法分析基本概念 算法運行所需要的計算機資源的量稱為算算法的復(fù)雜性法的復(fù)雜性。 計算算法運行所需資源量的過程稱為算法復(fù)雜性分析，簡稱為算法分析算法分析。 理論上，算法分析既要計算算法的時間復(fù)雜性，也要計算它的空間復(fù)雜性。 本書中除非特別說明，所說的算法分析，僅局限于對算法的時間復(fù)雜性分析。 隨機訪問計算機 RAM RAM只用一個處理機，卻有無限量的隨機存儲器。

2、它的有限個基本操作算術(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實例

3、在線性表A中查找。（a）查找值為x=1的元素，從A1起依次要進行5次檢測，第一次找到值為1的元素。（b）查找值為x=11的元素，從A1起依次檢測完所有元素（進行10次檢測），沒有找到值為11的元素最壞情形。（c）查找值為x=3的元素，從A1起僅進行一次檢測就找到值為3的元素最好情形。 4算法的漸進運行時間 當(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ù)）作為“標準”，研究極限： 若=非零常數(shù)，則稱（n）是T（n）的漸近表達式，或稱T（n）漸近等于（n），記

4、為 T（n）=（n），這個記號稱為算法運行時間的漸近-記號，簡稱為-記號。 )()(limnTnYn5有效算法 如果兩個算法運行時間的漸近表達式相同，則將它們視為具有相同時間復(fù)雜度的算法。顯然，漸近時間為對數(shù)冪的算法優(yōu)于漸近時間為冪函數(shù)的算法，而漸近時間為冪函數(shù)的算法則優(yōu)于漸近時間為指數(shù)函數(shù)的算法。我們把漸近時間為冪函數(shù)的算法稱為是具有多項式時間的算法多項式時間的算法，漸近時間不超過多項式的算法則稱其為有效的算法有效的算法。 6漸增型算法 漸增型算法漸增型算法有一個共同的特征：構(gòu)成算法的主體是一個循環(huán)結(jié)構(gòu)，它逐步將部分解擴張成一個完整解。該循環(huán)將遵循一個始終不變的原則：每次重復(fù)之初，總維持著問

5、題的一個部分解。我們將此特征稱為算法的循環(huán)不變量循環(huán)不變量。 1.2 插入排序算法 1問題的理解與描述 排序問題的形式化表示為： 輸入輸入：一組數(shù)。 輸出輸出：輸入的一個排列（重排），滿足a1a2, ., an。2算法的偽代碼描述 INSERTION-SORT （A） 1 for j 2 to lengthA 2 do key Aj 3 將Aj插入到排好序的序列A1 j - 1中。 4 i j - 1 5 while i 0 and Ai key 6 do Ai + 1 Ai 7 i i - 1 8 Ai + 1 keyINSERTION-SORT在A = 上的操作46783512345674

6、6835123456476835123456467835346785345678(a)(b)(c)(d)(e)(f)數(shù)組的下標表示在各方格的上方，存儲在數(shù)組中的數(shù)值表示在各方格內(nèi)。（a）（e）第18行的for循環(huán)的各次重復(fù)。每次重復(fù)中，黑色方格放的是鍵Aj，它在第5行中逐一與其左邊灰色方格內(nèi)的元素比較?；疑募^指示處在第6行中被右移一格的元素，黑色箭頭則指示出鍵在第8行移動到的位置。（f）最終排好序的數(shù)組。 3算法的正確性 循環(huán)不變量循環(huán)不變量 第第18行的行的for循環(huán)的每次重復(fù)之初，子序循環(huán)的每次重復(fù)之初，子序列列A1j - 1由原來由原來A1j - 1中的元素組中的元素組成，且已排好序

7、。成，且已排好序。 4算法的運行時間 假定序列A含有n個元素，對INSERTION-SORT而言，最壞情形是序列A初始狀態(tài)是降序排列。在此情形下，對第18行的for循環(huán)的n-1次重復(fù)的每一次，內(nèi)嵌的第57行的while循環(huán)將分別重復(fù)1，2，n-1次。所以，第67行的操作將重復(fù)進行1+2+n-1=n（n-1）/2次。于是，該算法的最壞情形時間用-記號表示為(n2)。1.3 兩個有序序列的合并算法 1問題的理解與描述 將兩個有序序列合并合并為一個有序序列問題的形式化表示為： 輸入輸入：序列Apr。其中，子序列Ap.q和Aq+1.r是有序的。 輸出輸出：Ap.r所有元素的重排，使之有序。2算法的偽代

8、碼描述MERGE(A, p, q, r)1 n1q - p + 12 n2 r - q3創(chuàng)建數(shù)組L1n1和R1n24 for i 1 to n15 do Li Ap + i - 16 for j 1 to n27do Rj Aq + j8 i 19 j 110 k p11 while i n1 and j n212 do if Li Rj13then Ak Li14 i i + 115 else Ak Rj16j j + 117 kk+118 if i n119 then 將Li. n1復(fù)制到Ak.r20 if j n221 then 將Rj. n2復(fù)制到Ak.r對序列A9.16 = 運行ME

9、RGE過程使用兩個輔助數(shù)組L和R進行合并操作。在復(fù)制后，數(shù)組L包含，數(shù)組R包含。A中深灰色的位置包含最終值，L和R中淺灰色位置包含的值尚未復(fù)制回A中。A的淺灰色位置是將被覆蓋的，而L和R中深灰色位置包含的是已經(jīng)被復(fù)制回A的值。(a)(g)是第1217行的while循環(huán)每次重復(fù)之初的A、L、R及其下標k、i、j。(h)是執(zhí)行了第1821將L中剩余的元素復(fù)制到Ak.r中。此時，子數(shù)組A916已經(jīng)排好序。 2457123624571236LRkijA1457123624571236LRkijA1257123624571236LRkijA1227123624571236LRkijA1223423624

10、571236LRkijA1223453624571236LRkijA1223456624571236LRkijA1223456724571236LRkijA(a)(b)(c)(d)(f)(e)(g)(h)981011121314151617123412349810111213141516171234123498101112131415161798101112131415161712341234123412349810111213141516179810111213141516171234123412341234981011121314151617123412349810111213141516

11法的正確性 循環(huán)不變量：循環(huán)不變量： 在第在第1217行的行的while循環(huán)的每次重復(fù)之初，循環(huán)的每次重復(fù)之初，子數(shù)組子數(shù)組Apk - 1包含包含L1n1和和R1n2中的中的k - p個最小的元素，并排好序。此外，個最小的元素，并排好序。此外，Li和和Rj分別是各自數(shù)組中尚未復(fù)制回數(shù)分別是各自數(shù)組中尚未復(fù)制回數(shù)組組A的元素中的最小者。的元素中的最小者。 可利用此循環(huán)不變量來證明合并算法可利用此循環(huán)不變量來證明合并算法MERGE是正確的。是正確的。1.4 序列的劃分 1問題的理解與描述 序列的劃分問題描述如下： 輸入輸入：序列Apr。 輸出輸出：下標q（p q r），原序

12、列Apr的一個重排：使得Apq中的元素值不超過Aq(=原Ar的值)，而Aq+1.r中的元素值均大于Aq。2算法的偽代碼描述 PARTITION(A, p, r) 1 x Ar 2 i p - 1 3 for j p to r - 1 4 do if Aj x 5 then i i + 1 6 exchange Ai Aj 7 exchange Ai + 1 Ar 8 return i + 1對一個樣本序列的劃分操作 （a）初始的序列和變量設(shè)置。沒有任何元素進入上述兩部分。（b）（h）表示第36行的for循環(huán)的每一次重復(fù)。黑色雙向箭頭表示第6行的元素交換操作。（i）表示上述循環(huán)終止后第7行執(zhí)行的元素交換操作。 82713564prij82713564p irj82713564p irj82713564p irj12783564prji12387564prji12387564prji12387564prji12387564prji(a)(b)(c)(d)(e)(f)(g)