第1章漸增型算法徐子珊

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

4．算法的運(yùn)行時(shí)間假定序列A含有n個(gè)元素，對(duì)INSERTION-SORT而言，最壞情形是序列A初始狀態(tài)是降序排列。在此情形下，對(duì)第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次。于是，該算法的最壞情形時(shí)間用Θ-記號(hào)表示為Θ(n2)。1.3兩個(gè)有序序列的合并算法1．問(wèn)題的理解與描述將兩個(gè)有序序列合并為一個(gè)有序序列問(wèn)題的形式化表示為：輸入：序列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]對(duì)序列A[9..16]=<2,4,5,7,1,2,3,6>運(yùn)行MERGE過(guò)程使用兩個(gè)輔助數(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í)，子數(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個(gè)最小的元素，并排好序。此外，L[i]和R[j]分別是各自數(shù)組中尚未復(fù)制回?cái)?shù)組A的元素中的最小者?？衫么搜h(huán)不變量來(lái)證明合并算法MERGE是正確的。1.4序列的劃分1．問(wèn)題的理解與描述序列的劃分問(wèn)題描述如下：輸入：序列A[p…r]。輸出：下標(biāo)q（p

q

r），原序列A[p…r]的一個(gè)重排：使得A[p…q]中的元素值不超過(guò)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對(duì)一個(gè)樣本序列的劃分操作（a）初始的序列和變量設(shè)置。沒(méi)有任何元素進(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ù)之初，對(duì)每一個(gè)數(shù)組下標(biāo)k，若p