第 1 章 漸增型算法 徐子珊

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

2、它的有限個(gè)基本操作算術(shù)運(yùn)算、邏輯運(yùn)算和數(shù)據(jù)的移動(dòng)（比如對(duì)變量的賦值）均在有限固定時(shí)間內(nèi)完成，假定所有這些基本操作都消耗一個(gè)時(shí)間單位。 算法在RAM上運(yùn)行所需的時(shí)間，顯然就是執(zhí)行基本操作的次數(shù)。 算法運(yùn)行時(shí)間的3種情形 對(duì)固定的輸入規(guī)模，使運(yùn)算時(shí)間最長的輸入所消耗的運(yùn)行時(shí)間稱為算法的最壞情形時(shí)間最壞情形時(shí)間。 對(duì)固定的輸入規(guī)模，使運(yùn)行時(shí)間最短的輸入所消耗的時(shí)間，稱為最好情形時(shí)間最好情形時(shí)間。 假定固定的輸入規(guī)模為n，所有不同輸入構(gòu)成的集合為Dn，對(duì)問題的每一個(gè)輸入為IDn，若已知該輸入發(fā)生的概率為P(I)，對(duì)應(yīng)的運(yùn)行時(shí)間為T(I)，運(yùn)行時(shí)間的數(shù)學(xué)期望值 稱為算法的平均情形時(shí)間平均情形時(shí)間。3實(shí)例

3、在線性表A中查找。（a）查找值為x=1的元素，從A1起依次要進(jìn)行5次檢測(cè)，第一次找到值為1的元素。（b）查找值為x=11的元素，從A1起依次檢測(cè)完所有元素（進(jìn)行10次檢測(cè)），沒有找到值為11的元素最壞情形。（c）查找值為x=3的元素，從A1起僅進(jìn)行一次檢測(cè)就找到值為3的元素最好情形。 4算法的漸進(jìn)運(yùn)行時(shí)間 當(dāng)n時(shí)，評(píng)估T（n）趨于無窮大的快慢來分析算法的時(shí)間復(fù)雜性。我們往往用幾個(gè)函數(shù)（n）：冪函數(shù)nk（k為正整數(shù)）、對(duì)數(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），記

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

5、題的一個(gè)部分解。我們將此特征稱為算法的循環(huán)不變量循環(huán)不變量。 1.2 插入排序算法 1問題的理解與描述 排序問題的形式化表示為： 輸入輸入：一組數(shù)。 輸出輸出：輸入的一個(gè)排列（重排），滿足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ù)組的下標(biāo)表示在各方格的上方，存儲(chǔ)在數(shù)組中的數(shù)值表示在各方格內(nèi)。（a）（e）第18行的for循環(huán)的各次重復(fù)。每次重復(fù)中，黑色方格放的是鍵Aj，它在第5行中逐一與其左邊灰色方格內(nèi)的元素比較。灰色的箭頭指示處在第6行中被右移一格的元素，黑色箭頭則指示出鍵在第8行移動(dòng)到的位置。（f）最終排好序的數(shù)組。 3算法的正確性 循環(huán)不變量循環(huán)不變量 第第18行的行的for循環(huán)的每次重復(fù)之初，子序循環(huán)的每次重復(fù)之初，子序列列A1j - 1由原來由原來A1j - 1中的元素組中的元素組成，且已排好序

7、。成，且已排好序。 4算法的運(yùn)行時(shí)間 假定序列A含有n個(gè)元素，對(duì)INSERTION-SORT而言，最壞情形是序列A初始狀態(tài)是降序排列。在此情形下，對(duì)第18行的for循環(huán)的n-1次重復(fù)的每一次，內(nèi)嵌的第57行的while循環(huán)將分別重復(fù)1，2，n-1次。所以，第67行的操作將重復(fù)進(jìn)行1+2+n-1=n（n-1）/2次。于是，該算法的最壞情形時(shí)間用-記號(hào)表示為(n2)。1.3 兩個(gè)有序序列的合并算法 1問題的理解與描述 將兩個(gè)有序序列合并合并為一個(gè)有序序列問題的形式化表示為： 輸入輸入：序列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對(duì)序列A9.16 = 運(yùn)行ME

9、RGE過程使用兩個(gè)輔助數(shù)組L和R進(jìn)行合并操作。在復(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及其下標(biāo)k、i、j。(h)是執(zhí)行了第1821將L中剩余的元素復(fù)制到Ak.r中。此時(shí)，子數(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個(gè)最小的元素，并排好序。此外，個(gè)最小的元素，并排好序。此外，Li和和Rj分別是各自數(shù)組中尚未復(fù)制回?cái)?shù)分別是各自數(shù)組中尚未復(fù)制回?cái)?shù)組組A的元素中的最小者。的元素中的最小者。 可利用此循環(huán)不變量來證明合并算法可利用此循環(huán)不變量來證明合并算法MERGE是正確的。是正確的。1.4 序列的劃分 1問題的理解與描述 序列的劃分問題描述如下： 輸入輸入：序列Apr。 輸出輸出：下標(biāo)q（p q r），原序

12、列Apr的一個(gè)重排：使得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對(duì)一個(gè)樣本序列的劃分操作 （a）初始的序列和變量設(shè)置。沒有任何元素進(jìn)入上述兩部分。（b）（h）表示第36行的for循環(huán)的每一次重復(fù)。黑色雙向箭頭表示第6行的元素交換操作。（i）表示上述循環(huán)終止后第7行執(zhí)行的元素交換操作。 82713564prij82713564p irj82713564p irj82713564p irj12783564prji12387564prji12387564prji12387564prji12387564prji(a)(b)(c)(d)(e)(f)(g)