算法設(shè)計(jì)與分析課件

演算法分析基本概念

*1.1 引言DonaldE.Knuth電腦科學(xué)就是演算法研究例，編譯程序和操作系統(tǒng)是具有特定目標(biāo)的演算法的直接實(shí)現(xiàn)。**演算法（Algorithm） 解題方案的準(zhǔn)確完整的描述，是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。①無(wú)論是解題思路還是編寫(xiě)程式，都是在實(shí)施某種演算法。前者是推理實(shí)現(xiàn)，後者是操作實(shí)現(xiàn)。②演算法不是程式，但演算法是用程式或程式偽代碼來(lái)描述的。演算法分析（AlgorithmAnalysis）演算法分析是研究演算法一旦轉(zhuǎn)換成某種語(yǔ)言的程式，該程式在電腦上運(yùn)行需要多少時(shí)間和存儲(chǔ)空間，才能完成解題方案。*

確定一個(gè)程式的運(yùn)行效率，可使用數(shù)學(xué)分析方法，也可使用實(shí)驗(yàn)測(cè)試方法，以期在理論和實(shí)踐作出評(píng)價(jià)。1.2 歷史背景20世紀(jì)早期，能否用一種有效的過(guò)程（演算法）來(lái)求解問(wèn)題受到廣泛關(guān)注，人們的注意力是放在問(wèn)題的可解和不可解的分類上。問(wèn)題的可判定性和可解性的研究領(lǐng)域稱為“可計(jì)算理論”。數(shù)字電腦出現(xiàn)以後，由於有限的資源，提出了盡可能少用資源的有效演算法的需求，導(dǎo)致出現(xiàn)計(jì)算複雜性的新領(lǐng)域。“計(jì)算複雜性”是研究可解類問(wèn)題的效率，所謂效率是指解決問(wèn)題所需的時(shí)間和空間。*1.3 二分搜索㈠順序搜索（線性搜索） 問(wèn)題：設(shè)A[1..n]為一個(gè)n個(gè)元素（整數(shù)）的數(shù)組，判定給定元素x是否在A中。演算法：掃描A的所有專案，將每個(gè)專案與x比較，如果在第j次比較後（1≤j≤n）搜索成功，即x=A[j]，則返回j值；否則返回0，表示沒(méi)有找到。這種方法稱為順序搜索。*演算法1.1LinearSearch（Page3）輸入：n個(gè)元素的數(shù)組A[1..n]和元素x。輸出：如果x=A[j]，1≤j≤n，則輸出j，否則輸出0。1. j←12. while(j<n)and(x≠A[j])3. j←j+14. endwhile5. if(x=A[j])thenreturnjelsereturn0*出迴圈分析：

①x=A[j]，此時(shí)j<n。

②j等於n，但A[n]與x尚未比較。1.j←1while(j≤n)if(x=A[j])thenreturnj

j←j+15.endwhilereturn0㈡順序搜索法分析

最少比較次數(shù)為1，最多比較次數(shù)為n。㈢二分搜索令A(yù)[low..high]為元素按昇冪排列的非空數(shù)組，數(shù)A[mid]為中間元素。假定x>A[mid]，如果x在A中，則它必定是

A[mid+1]，A[mid+2]，…，A[high]中的一個(gè)，接下來(lái)只需在A[mid+1..high]中搜索x。換句話說(shuō)，A[low..mid]中的專案在後續(xù)比較中被掉棄了。類似地，如果x<A[mid]，只需在A[low..mid-1]中搜索x。由於重複進(jìn)行二等分，導(dǎo)致了一個(gè)稱為二分搜索的有效策略。*演算法1.2BinarySearch（Page4）輸入：n個(gè)元素的數(shù)組A[1..n]（按昇冪排列）和元素x。輸出：如果x=A[j]，1≤j≤n，則輸出j，否則輸出0。1. low←1:high←n:j←02. while(low≤high)and(j=0)3. mid←

(low+high)/2

//取整4. if(x=A[mid])thenj←mid elseif(x<A[mid])thenhigh←mid-16. elselow←mid+1 //x>A[mid]7. endwhile8. returnj**1457891012152223273235A[1..14]=A[8..14]=121522A[8..10]=①要搜索元素x=22。首先將x與A的中間元素比較，A[(1+14)/2]=A[7]=10，由於x>A[7]，可以把A[1..7]掉棄。②在剩餘元素A[8..14]中搜索x，A[(8+14)/2]=A[11]=23，由於x<A[11]，可以把A[11..14]掉棄。12152223273235考慮搜索數(shù)組1 7 148 11 1489 10*A[10]=22③在剩餘元素A[8..10]中搜索x，A[(8+10)/2]=A[9]=15，由於x>A[9]，可以把A[8..9]掉棄。④留在序列中僅剩一個(gè)項(xiàng)目A[10]=22，最後找到x=A[10]，搜索成功完畢（若x≠A[10]，則low≤high條件不成立，出迴圈）。10121522A[8..10]=89 10*㈣二分搜索法分析假定每個(gè)三向比較(if-then-else)計(jì)為一次比較，顯然最小比較次數(shù)為1，即搜索元素x在序列中間位置。為了計(jì)算最大比較次數(shù)，不失一般性，可假定x≥A[high]。①第2次迭代前（即第1次迭代結(jié)束後）數(shù)組A中剩餘元素 若n是偶數(shù)，A[(mid+1)..n]共有n/2個(gè)元素。 若n是奇數(shù)，A[(mid+1)..n]共有(n-1)/2個(gè)元素。二種情況都有：A[mid+1..n]=

n/2

=

n/22-1

②第3次迭代前數(shù)組A中剩餘元素

n/2

/2

=

n/4

=

n/22

=

n/23-1

③第j次迭代前數(shù)組A中剩餘元素

n/2j-1

④搜索x的終止條件是餘下元素僅僅為1個(gè)，即

n/2j-1

=1n=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

)。

當(dāng)

n/2j-1

=1，j為最大迭代次數(shù)（最大循環(huán)次數(shù)、最大比較次數(shù)）

n/2j-1

=1等價(jià)於1≤n/2j-1<2等價(jià)於2j-1≤n<2j等價(jià)於（取對(duì)數(shù)）j-1≤Log2n<j考慮

Log2n

≤Log2n<

Log2n

+1因?yàn)閖是整數(shù)，故有j-1=

Log2n

或j=

Log2n

+1二者均有j=

Log2n

+1*105 231 8 15 32 4 7 9 12 22 27 35*

可將二分搜索法的執(zhí)行描述為決策樹(shù)，紅色的結(jié)點(diǎn)是與x=22相比較的數(shù)字。

14578912152223273235

定理1.1（Page6）對(duì)於一個(gè)大小為n的已排序數(shù)組，演算法BinarySearch執(zhí)行比較的最大次數(shù)為:

Log2n

+1*注：由於if-then-else嵌套使用，最大比較次數(shù)實(shí)質(zhì)上應(yīng)為迭代次數(shù)2倍，即2(

Log2n

+1)。如果考慮while語(yǔ)句的比較次數(shù)，則最大比較次為4(

Log2n

+1)。x首先與10比較，由於22比10大，故與23比較。以此類推，直至22。

決策樹(shù)的高度為

Log2n

，由決策樹(shù)可知，二分搜索法的最大比較次數(shù)是

Log2n

+1。1.4合併二個(gè)已排序的表㈠演算法描述

假定有一個(gè)數(shù)組A[1..m]，p，q，r是它的三個(gè)索引，並有1≤p≤q<r≤m，二個(gè)子數(shù)組A[p..q]和A[q+1..r]各自按昇冪排列，重新排列A中元素的位置，使得子數(shù)組A[p..r]按昇冪排列。①使用二個(gè)指針s和t，初始化時(shí)s=p、t=q+1，s和t各自指向A[p]和A[q+1]，空數(shù)組B[p..r]用作暫存器。②每一次比較元素A[s]和A[t]，將小的元素添加到B中。然後更新指針，若A[s]≤A[t]，則s加1，否則t加1。③當(dāng)s=q+1，說(shuō)明子數(shù)組A[p..q]的全部元素已進(jìn)入B，無(wú)需再比較，此時(shí)把子數(shù)組餘下部分A[t..r]添加到B中。④當(dāng)t=r+1，說(shuō)明子數(shù)組A[q+1..r]的全部元素已進(jìn)入B，無(wú)需再比較，此時(shí)把子數(shù)組餘下部分A[s..q]添加到B中。⑤最後將B[p..r]複製到A[p..r]。*過(guò)程1.3Merge（Page6）輸入：數(shù)組A[1..m]和它的三個(gè)索引p，q，r，1≤p≤q<r≤m，二個(gè)子數(shù)組A[p..q]和A[q+1..r]各自按昇冪排列。輸出：子數(shù)組A[p..r]按昇冪排列。0.procedureMerge(A[1..m],p,q,r)1. comment:B[p..r]是個(gè)輔助數(shù)組 //或B[1..m]2. s←p:t←q+1:k←p //s和t分別指向數(shù)組A二個(gè)子數(shù)組元素3. while(s≤q)and(t≤r) //k指向數(shù)組B當(dāng)前空白元素位置4. ifA[s]≤A[t]thenB[k]←A[s]:s←s+15. elseB[k]←A[t]:t←t+16. endif7. k←k+1 //指向數(shù)組B下一個(gè)空白位置8. endwhile9. ifs=q+1thenB[k..r]←A[t..r]//說(shuō)明子數(shù)組A[p..q]元素已處理完10. elseB[k..r]←A[s..q]//否則t=r+1，說(shuō)明子數(shù)組A[q+1..r]已處理完。11. endif12. A[p..r]←B[p..r] //複製13.endprocedure**2316711134557qrkt0.procedureMerge(A[1..m],p,q,r)1. comment:B[p..r]是個(gè)輔助數(shù)組2. s←p:t←q+1:k←p 3. while(s≤q)and(t≤r)4. ifA[s]≤A[t]thenB[k]←A[s]:s←s+15. elseB[k]←A[t]:t←t+16. endif7. k←k+18. endwhile9. ifs=q+1thenB[k..r]←A[t..r]10. elseB[k..r]←A[s..q]11. endif12. A[p..r]←B[p..r]13.endprocedurespA[p..r]=A[p..q]+A[q+1..r]B[p..r]*㈡算法分析設(shè)有個(gè)數(shù)分別為n1和n2的二個(gè)子數(shù)組n1+n2=n，如果子數(shù)組A[p..q]中每個(gè)元素均小于另一個(gè)子數(shù)組A[q+1,r]中的所有元素，例，要合併下麵二個(gè)子數(shù)組：236711134557

該演算法只需執(zhí)行3次比較，即n1次比較。另一方面，比較次數(shù)最多為n-1=n1+n2-1次。例如要合併下麵二個(gè)子數(shù)組：2366711134557就需要7次比較。所以，演算法Merge的最少比較次數(shù)是n1，最大比較次數(shù)為n-1。*觀察結(jié)論1.1（Page7）執(zhí)行演算法Merge，將個(gè)數(shù)分別為n1和n2的非空數(shù)組合並成一個(gè)為n=n1+n2的排序數(shù)組。設(shè)n1≤n2

，元素的比較次數(shù)在n1和n-1之間。特例，如果二個(gè)數(shù)組大小為

n/2

和

n/2

，需要比較的最大次數(shù)在

n/2

和n-1之間。觀察結(jié)論1.2（Page7）執(zhí)行算法Merge，將個(gè)數(shù)分別為n1和n2的非空數(shù)組合並成一個(gè)為n=n1+n2的排序數(shù)組，元素的賦值次數(shù)恰好是2n。1.5 選擇排序法㈠選擇演算法假定有一個(gè)數(shù)組A[1..n]，A[i..n]是它的一個(gè)子數(shù)組，1≤i<n。編寫(xiě)一函數(shù)，作用為：從A[i..n]中選擇一個(gè)最小的數(shù)A[k]（i<k≤n），將A[i]和A[k]互換（若k=i，無(wú)需交換）。過(guò)程Selection(參見(jiàn)Page8)輸入：A[i..n]輸出：A[i..n]，其中A[i]為A[i..n]中的最小的數(shù)。0.procedureSelection(i)1. k←i2. forj←i+1ton3. ifA[j]<A[k]thenk←j4. endfor5. ifk≠ithen交換A[i]和A[k] 6.endprocedure **㈡選擇排序算法設(shè)A[1..n]為n個(gè)元素的數(shù)組，選擇排序演算法如下：

①首先找到最小元素，並將其存放在A[1]中。

②然後在剩下的n-1個(gè)元素中找到最小元素，將其存放在A[2]中。

③重複此過(guò)程，直至找到第二大元素，並將其存放在A[n-1]中。演算法1.4SelectionSort（參見(jiàn)Page8）輸入：數(shù)組A[1..n]輸出：按昇冪排列的數(shù)組A[1..n]1. fori←1ton-12. Selection(i)endfor *㈢選擇排序演算法分析

這個(gè)演算法執(zhí)行的元素比較次數(shù)為：可以看出元素的交換次數(shù)界於0和n-1之間，由於每次交換需要3次元素賦值，因此元素賦值次數(shù)界於0和3(n-1)之間。觀察結(jié)論1.3(Page8)

執(zhí)行演算法SelectionSort所需的元素比較次數(shù)為n(n-1)/2，元素的賦值次數(shù)界於0與3(n-1)之間。1.6插入排序㈠插入演算法假定有一個(gè)數(shù)組A[1..n]，A[1..i]是它的一個(gè)子數(shù)組，1<i≤n。A[1..i-1]已按昇冪排列。編寫(xiě)一函數(shù)，作用為：將x=A[i]插入到子數(shù)組A[1..i-1]中，使得A[1..i]按昇冪排列。依次掃描序號(hào)從j=i-1到j(luò)=1的元素，將x和A[j]比較。在掃描的每一步，元素都被移到序號(hào)更高的一個(gè)位置上，這種過(guò)程直到以下情況出現(xiàn)時(shí)終止：

①找到一個(gè)小於等於A[i]的元素A[j] ②元素A[1]已掃描過(guò)此時(shí)可將x插入到A[j]（A[j]已移入A[j+1]）。**過(guò)程Insertion（參見(jiàn)9）輸入：A[1..i-1]已按昇冪排列 輸出：A[1..i]按昇冪排列0.procedureInsertion(i)1. x←A[i]2. j←i-13. while(j>0)and(A[j]>x)4. A[j+1]←A[j]5. j←j-16. endwhile 7. A[j+1]←x8.endprocedure *㈡插入排序算法

設(shè)A[1..n]為n個(gè)元素的數(shù)組，插入排序演算法描述如下：

①?gòu)淖訑?shù)組A[1]開(kāi)始，它自然是已排序好的。

②接下來(lái)，將A[2]插入到A[1]的前面或後面。

③然後，再將A[3]插入到A[1..2]中。

④直到A[n]插入到A[1..n-1]中為止。演算法1.6InsertionSort(參見(jiàn)9)輸入：數(shù)組A[1..n]輸出：按昇冪排列的數(shù)組A[1..n]1. fori←2ton2. Insertion(i)endfor *㈢插入排序算法分析執(zhí)行InsertionSort，元素比較次數(shù)取決於輸入元素的順序。①當(dāng)序列已按昇冪排列時(shí)，元素比較次數(shù)最小，僅為n-1，每個(gè)元素A[i]（2≤i≤n）只和A[i-1]比較。②當(dāng)元素已按降序排列，並且所有元素各不相同，比較次數(shù)為最大。如下所示：

因?yàn)槊總€(gè)元素A[i](2≤i≤n)都和子序列A[1..i-1]中的每個(gè)元素比較，這一結(jié)果與演算法SelectionSort相一致。*觀察結(jié)論1.4（Page9）執(zhí)行算法InsertionSort的元素比較次數(shù)在n-1到n(n-1)/2之間。元素賦值次數(shù)等於元素比較次數(shù)加上n-1。說(shuō)明：若原全部元素已按昇冪排列，在Insertion過(guò)程中，每次僅需一次比較，故總比較次數(shù)為n-1，迴圈中的賦值不執(zhí)行。因?yàn)樵诔鲛捜︶嵊幸淮钨x值，所以此時(shí)元素賦值總的次數(shù)為n-1。若原全部元素已按降序排列，在Insertion過(guò)程中，出迴圈由(j>0)不成立引起，此時(shí)元素總的比較次數(shù)為n(n-1)/2，所以循環(huán)體中元素賦值總的次數(shù)為n(n-1)/2?？紤]出迴圈後賦值，此時(shí)元素賦值總次數(shù)應(yīng)為n(n-1)/2+n-1。*“選擇排序法”和“插入排序法”小結(jié)輸入：A[1..i-1]已按昇冪排列輸出：A[1..i]按昇冪排(1)選擇法（往後選擇）

Seletion(i)

從A[i..n]中選擇一個(gè)最小的數(shù)，將其和A[i]交換，使得A[1..i]有序。(2)插入法（向前插入）

Insertion(i)

將A[i]中的元素插入到A[1..i]中一個(gè)合適位置，使得A[1..i]有序。*245994521746492517461467124456791.7 自底向上合并排序㈠引入插入和選擇排序法的最大比較次數(shù)都與n2成正比，從這個(gè)意義上來(lái)說(shuō)二種演算法的效率都是比較低的，考慮下麵的排序方法：㈡自底向上合併排序演算法

設(shè)A[1..n]為需排序的n個(gè)元素的數(shù)組①第1次迭代生成個(gè)數(shù)為2（=21）的排序序列，該序列共有=個(gè)。若剩餘1個(gè)元素，則讓它進(jìn)入下一輪合併。*945217464925174694521744925174②第2次迭代生成個(gè)數(shù)為4（=22）的排序序列，共有=個(gè)。若剩餘1或2個(gè)，則讓它進(jìn)入下一輪合併。如果剩餘3個(gè)，則將2個(gè)元素（已排序）和另外1個(gè)元素合併成一個(gè)3元素的排序序列。*245949251746146724594925174147

③第j次迭代（假設(shè)j=3）生成元素個(gè)數(shù)為2j個(gè)的排序序列，該序列共有個(gè)，可能剩餘的元素個(gè)數(shù)k，其大小在1至2j-1之間。若1≤k≤2j-1，則讓它們進(jìn)入下一次合併（局部已有序）。若2j-1＜k＜2j，則將2j-1個(gè)元素（局部已有序）和另外k-2j-1個(gè)元素（局部已有序）合併成個(gè)數(shù)為k的排序序列。*剩餘元素為7個(gè)245914671244567924591471244579④總的迭代次數(shù)j的值範(fàn)圍為：2j-1<n≤2j

。*演算法1.6BottomUpSort（Page10）輸入：n個(gè)元素的數(shù)組A[1..n]輸出：按昇冪排列的數(shù)組A[1..n]1. t←12. whilet<n3. s←t:t←2s:i←0//i表示要處理數(shù)據(jù)的起始地址(簡(jiǎn)稱位移)4. whilei+t≤n5. Merge(A,i+1,i+s,i+t)

//Merge(A,p,q,r)6. i←i+t //i表示要處理數(shù)據(jù)的起始地址(簡(jiǎn)稱位移)7. endwhile8. ifi+s<nthenMerge(A,i+1,i+s,n)

endwhile //n-i>s表示剩余的元素個(gè)數(shù)大于被合并的子序列長(zhǎng)度s為被合併的子序列長(zhǎng)度，初始時(shí)為1，每迴圈一次乘以2。t為s的二倍，即二個(gè)子序列合併後的長(zhǎng)度，可省略(見(jiàn)下頁(yè))。當(dāng)n不是t的整數(shù)倍，出內(nèi)層迴圈後執(zhí)行第8步。如果剩餘元素?cái)?shù)目大於s，就要將最後一個(gè)長(zhǎng)度為s的子序列和剩餘元素進(jìn)行一次合併排序，此時(shí)二個(gè)子序列合併後的長(zhǎng)度小於t=2s。*61095311481276105931148127569103481112734568910111271234567891011㈢示例

當(dāng)n不是2的整數(shù)冪時(shí)，自底向上合併排序的過(guò)程如下所示：*第1次迭代：t=1＜n=11成立

s=1,t=2i值的範(fàn)圍：0,2,4,8 i=0 MERGE(A,1,1,2) i=2 MERGE(A,3,3,4) i=4 MERGE(A,5,5,6) i=6 MERGE(A,7,7,8) i=8 MERGE(A,9,9,10) i=10時(shí)，i+t≤11不成立，出迴圈。出迴圈後，i+s=10+1＜n=11不成立，因此不再合併，最後一個(gè)序列長(zhǎng)度為1（或稱剩下的元素個(gè)數(shù)）。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長(zhǎng)度（即合併前）t表示合併後序列的長(zhǎng)度（初值為1）i表示位移61095311481276105931148127*第2次迭代：t=2＜n=11成立

s=2,t=4i值的範(fàn)圍：0,4,8 i=0 MERGE(A,1,2,4) i=4 MERGE(A,5,6,8) i=8時(shí)，i+t≤11不成立，出迴圈。出迴圈後，i+s=8+2＜n=11成立，執(zhí)行MERGE(A,9,10,11)，最後一個(gè)序列長(zhǎng)度為3。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長(zhǎng)度（即合併前）t表示合併後序列的長(zhǎng)度（初值為1）i表示位移61059311481275691034811127*第3次迭代：t=4＜n=11成立

s=4,t=8i值的範(fàn)圍：0,8 i=0 MERGE(A,1,4,8) i=8時(shí)，i+t≤11不成立，出迴圈。出迴圈後，i+s=8+4＜n=11不成立，因此不再合併，最後一個(gè)序列長(zhǎng)度為3。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長(zhǎng)度（即合併前）t表示合併後序列的長(zhǎng)度（初值為1）i表示位移56910348111273456891011127*第4次迭代：t=8＜n=11成立

s=8,t=16i值的範(fàn)圍：0 i=0時(shí)，i+t≤11不成立，出迴圈。出迴圈後，i+s=0+8＜n=11成立，執(zhí)行MERGE(A,1,8,11)。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長(zhǎng)度（即合併前）t表示合併後序列的長(zhǎng)度（初值為1）i表示位移34568910111271234567891011第5次迭代：t=16＜n=11不成立，終止執(zhí)行。*演算法1.6BottomUpSort（省略變數(shù)t）輸入：n個(gè)元素的數(shù)組A[1..n]輸出：按昇冪排列的數(shù)組A[1..]1. s←1 //s表示被合併序列的長(zhǎng)度（即合併前）

2. whiles<n //2s表示合併後序列的長(zhǎng)度（s初值為1）

3. i←04. whilei+2*s≤n5. Merge(A,i+1,i+s,i+2s)6. i←i+2s7. endwhile8. ifi+s<nthenMerge(A,i+1,i+s,n)9.

s←2s

10. endwhile*㈣自底向上合併排序演算法分析

假設(shè)數(shù)組元素個(gè)數(shù)n為2的冪，外部迴圈次數(shù)為k=log2n。在執(zhí)行內(nèi)部迴圈後，由於n為2的冪，故第8步永遠(yuǎn)不會(huì)執(zhí)行。①在第1次迭代中，共執(zhí)行了n/2次比較。n個(gè)元素被劃分為n/2個(gè)段（段長(zhǎng)=2），段內(nèi)有序。②在第2次迭代中，n/2個(gè)段（段長(zhǎng)=2）元素序列被合併成n/4個(gè)段（段長(zhǎng)=4），段內(nèi)有序。根據(jù)觀察結(jié)論1.1（Page7），每對(duì)合併需要的比較次數(shù)，最少為2，最多為3。③在第3次迭代中，n/4個(gè)段（段長(zhǎng)=4）元素序列被合併成n/8個(gè)段（段長(zhǎng)=8），段內(nèi)有序。根據(jù)觀察結(jié)論1.1（Page7），每對(duì)合併需要的比較次數(shù)，最少是4，最多7。*最少比較次數(shù)（k=log2n）④在第j次迭代中，個(gè)段（段長(zhǎng)=2j-1）元素序列被合併成個(gè)段（段長(zhǎng)=2j），段內(nèi)有序。根據(jù)觀察結(jié)論1.1（Page7），每對(duì)合併需要的比較次數(shù)，最少是2j-1，最多為2j-1。*最多比較次數(shù)(k=log2n)（共k項(xiàng)）*觀察結(jié)論1.5（Page11)

用演算法BottomUpSort對(duì)n個(gè)元素進(jìn)行排序，當(dāng)n為2的整數(shù)冪時(shí)，比較次數(shù)在(nlog2n)/2到nlog2n-n+1之間。執(zhí)行該演算法的元素賦值次數(shù)為2nlog2n。1.8時(shí)間複雜性

在計(jì)算複雜性領(lǐng)域中，主要是研究一個(gè)演算法所需要的時(shí)間和空間。即當(dāng)給出合法的輸入時(shí)，為了得到輸出，該演算法執(zhí)行時(shí)所需要的時(shí)間和空間，其中時(shí)間尤為重要。執(zhí)行演算法BottomUpSort的最大比較次數(shù)nlog2n-n+1執(zhí)行演算法SelectionSort的最大比較次數(shù)n(n-1)/2

假設(shè)一次比較所需的時(shí)間為10-6秒，當(dāng)數(shù)據(jù)個(gè)數(shù)n分別為27=128和220=1048576時(shí)，二個(gè)演算法執(zhí)行所耗費(fèi)的時(shí)間上限如下表所示：*nSelectionSortBottomUpSort2710-6*128(128-1)/2≈0.008秒10-6*(128*7-128+1)≈0.0008秒22010-6*220*(220-1)/2≈6.4天10-6*(220*20-220+1)≈20秒㈠概述

稱“一個(gè)演算法A對(duì)於輸入x要用y秒來(lái)運(yùn)行”是沒(méi)有意義的，也是沒(méi)有必要的。因?yàn)橛绊懸粋€(gè)演算法的實(shí)際運(yùn)行時(shí)間與諸多因素有關(guān)（例機(jī)器性能、語(yǔ)言選擇、編譯程序優(yōu)劣、程式員素質(zhì)等），甚至無(wú)需計(jì)算出演算法運(yùn)行時(shí)間的近似數(shù)，理由：①演算法分析通常是將解決同一問(wèn)題的各種演算法進(jìn)行相互比較，執(zhí)行時(shí)間是相對(duì)的，而不是絕對(duì)的。②演算法可以用各種語(yǔ)言來(lái)表示，甚至使用人類語(yǔ)言。③演算法應(yīng)獨(dú)立於機(jī)器，無(wú)論科技如何進(jìn)步，對(duì)演算法運(yùn)行時(shí)間的評(píng)估始終成立。④演算法分析不拘泥小規(guī)模數(shù)據(jù)的輸入，主要關(guān)心在大的輸入實(shí)例時(shí)，演算法運(yùn)行狀況。例某一演算法運(yùn)行時(shí)間為2n3，當(dāng)n變得很大時(shí)，常數(shù)2將不起作用。觀察函數(shù)n2log2n+10n2+n

中的低階項(xiàng)10n2和n

，當(dāng)n值越大，10n2+n對(duì)函數(shù)值的影響就越小。**①漸近運(yùn)行時(shí)間去除表示演算法運(yùn)行時(shí)間函數(shù)的低價(jià)項(xiàng)和首項(xiàng)係數(shù)（常數(shù)）。②時(shí)間複雜性在演算法分析中通常是用漸近運(yùn)行時(shí)間來(lái)度量一個(gè)演算法，漸近運(yùn)行時(shí)間通常稱為時(shí)間複雜性。③演算法分析中的漸近符號(hào)有：O、Ω、Θ、o。④表示時(shí)間複雜性的常用函數(shù)有： 常數(shù)： 1 運(yùn)行時(shí)間為恒定值，和輸入無(wú)關(guān)。 次線性函數(shù)：log2n（簡(jiǎn)記為logn)

線性函數(shù)： n

次平方函數(shù)：nlog2n（簡(jiǎn)記為nlogn)

平方函數(shù)： n2

立方函數(shù)： n3

指數(shù)函數(shù)： 2n 運(yùn)行時(shí)間是爆炸性的 階乘函數(shù)（超指數(shù)函數(shù)）：n! 運(yùn)行時(shí)間是爆炸性的*定義1.2（Page16）令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。如果存在一個(gè)自然數(shù)n0和一個(gè)正常數(shù)c，使得

n≥n0

，f(n)≤cg(n)則稱f(n)=O(g(n))，n0稱為閾值。㈡O符號(hào)（讀作大O）

若極限為非0正常數(shù)，則函數(shù)f(n)和g(n)增長(zhǎng)速度至多相差常數(shù)倍，或稱為同一級(jí)別；若極限為0，說(shuō)明隨著n的增大，函數(shù)f(n)的增長(zhǎng)要比g(n)的增長(zhǎng)慢得多。正常數(shù)，可以是0。*例1：f(n)=3n+2，求g(n)，使得f(n)=O(g(n))。解1： 當(dāng)n≥2，f(n)=3n+2≤3n+n=4n

令g(n)=n，當(dāng)n≥2時(shí)有f(n)≤4g(n) ∵f(n)≤4g(n) ∴f(n)=O(g(n))=O(n)解2：令g(n)=n同理可證：f(n)=O(nk)，k≥1*例2：f(n)=10n2+4n+2，求g(n)，使得f(n)=O(g(n))。解1： 當(dāng)n≥2，有f(n)≤10n2+4n+n=10n2+5n

當(dāng)n≥5，有f(n)≤10n2+5n≤10n2+n2=11n2

令g(n)=n2，因?yàn)楫?dāng)n≥5時(shí)有f(n)≤11g(n)

所以f(n)=O(g(n))=O(n2)解2：令g(n)=n2同理可證：f(n)=O(nk)，k≥2*例3：f(n)=6*2n+n2，求g(n)，使得f(n)=O(g(n))。解： 當(dāng)n≥4，有n2≤2n

故當(dāng)n≥4，有f(n)=6*2n+n2≤6*2n+2n=7*2n

令g(n)=2n，因?yàn)楫?dāng)n≥4時(shí)有f(n)≤7g(n)

所以f(n)=O(g(n))=O(2n)O符號(hào)提供了運(yùn)行時(shí)間的上界。演算法InsertionSort執(zhí)行的比較次數(shù)最多為cn2（=n(n-1)/2），c為某個(gè)適當(dāng)選擇的常數(shù)，可稱該演算法的運(yùn)行時(shí)間是O(n2)。只要當(dāng)排序元素的個(gè)數(shù)不小於某個(gè)閾值n0時(shí)，運(yùn)行時(shí)間最多為cn2。應(yīng)強(qiáng)調(diào)的是，即使當(dāng)輸入很大時(shí)，也不能說(shuō)運(yùn)行時(shí)間恰好為O(n2)，因?yàn)楫?dāng)輸入已經(jīng)按昇冪排列，演算法InsertionSort執(zhí)行的比較次數(shù)為n-1。*㈢Ω符號(hào)（讀作omiga）定義1.3（Page16）令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。如果存在一個(gè)自然數(shù)n0和一個(gè)正常數(shù)c，使得

n≥n0

，f(n)≥cg(n)則稱f(n)=Ω(g(n))，n0稱為閾值。

若極限是一個(gè)正常數(shù)，說(shuō)明函數(shù)f(n)的增長(zhǎng)速度和函數(shù)g(n)相差整數(shù)倍，基本為同一級(jí)別；若極限為∞，說(shuō)明隨著n的增大，函數(shù)f(n)增長(zhǎng)的速度要比g(n)快得多。可以是正常數(shù)或∞*例1：f(n)=3n+2，求g(n)，使得f(n)=Ω(g(n))。解： 當(dāng)n>0，f(n)=3n+2≥3n。 令g(n)=n，因?yàn)楫?dāng)n>0時(shí)有f(n)≥3g(n)

所以f(n)=Ω(g(n))=Ω(n)例2：f(n)=10n2+4n+2，求g(n)，使得f(n)=Ω(g(n))。解：令g(n)=n同理可證：f(n)=Ω(nk)，0≤k≤2*在常數(shù)因數(shù)範(fàn)圍內(nèi)，O符號(hào)提供了運(yùn)行時(shí)間上界，而Ω符號(hào)提供了運(yùn)行時(shí)間下界。稱演算法InsertionSort的元素比較次數(shù)至少是cn（=n-1

），c為某一合適的常數(shù)。在這種情況下，稱演算法InsertionSort的運(yùn)行時(shí)間是Ω(n)。無(wú)論何時(shí)，當(dāng)排序元素個(gè)數(shù)不小於某一個(gè)閾值n0時(shí)，運(yùn)行時(shí)間至少是cn。稱排序問(wèn)題的比較次數(shù)為Ω(nlog

n)，是指無(wú)法設(shè)計(jì)出一個(gè)新的基於比較的排序演算法，它的時(shí)間複雜性小於nlog

n。Ω符號(hào)定義的一個(gè)重要推論：

f(n)=Ω(g(n))，當(dāng)且僅當(dāng)g(n)=O(f(n))*㈣Θ符號(hào)（讀作theta）定義1.4（Page16）令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。如果存在一個(gè)自然數(shù)n0和二個(gè)正常數(shù)c1和c2，使得

n≥n0

，c1g(n)≤f(n)≤c2g(n)則稱f(n)=Θ(g(n))，n0稱為閾值。Θ符號(hào)定義的一個(gè)重要推論：f(n)=Θ(g(n))當(dāng)且僅當(dāng)f(n)=O(g(n))并且g(n)=O(f(n))

極限是一個(gè)正常數(shù)，說(shuō)明函數(shù)f(n)的增長(zhǎng)速度和函數(shù)g(n)的增長(zhǎng)速度相差整數(shù)倍，基本為同一級(jí)別。*例：f(n)=3n+2，求g(n)，使得f(n)=Θ(g(n))。解： 當(dāng)n≥2，f(n)=3n+2≤3n+n=4n

當(dāng)n≥1，f(n)=3n+2≥3n

故當(dāng)n≥2，有3n≤f(n)≤4n

令g(n)=n，因?yàn)楫?dāng)n≥2時(shí)有3g(n)≤f(n)≤4g(n)

所以f(n)=Θ(n)解2：令g(n)=n*Θ符號(hào)提供了演算法運(yùn)行時(shí)間的精確描述，由於演算法InsertionSort的運(yùn)行時(shí)間由線性到平方排列，因此不能用Θ描述。而SelectionSort演算法和BottomUpSort演算法可分別使用Θ(n2)和Θ(nlog2n)精確描述。

f(n)=Θ(g(n))是一個(gè)等價(jià)關(guān)係，由這個(gè)關(guān)係導(dǎo)出一個(gè)等價(jià)類，稱為複雜性類。例：f(n)=3n+2、g(n)=n，顯然有f(n)=Θ(g(n))。表示這二個(gè)函數(shù)屬同一複雜性類。㈤o符號(hào)（讀作小o）由等價(jià)關(guān)係f(n)=Θ(g(n))

導(dǎo)出了一個(gè)等價(jià)類，為了說(shuō)明二個(gè)函數(shù)屬於不同類，引入了o符號(hào)。f(n)=o(g(n))，當(dāng)且僅當(dāng)f(n)=O(g(n))，但g(n)≠O(f(n))。*定義1.3（Page19）

令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。如果對(duì)於每一個(gè)常數(shù)c>0，存在一個(gè)自然數(shù)n0，使得

n≥n0

，f(n)<cg(n)則稱f(n)=o(g(n))。

形式地說(shuō)明了當(dāng)n→∞時(shí)，f(n)對(duì)於g(n)來(lái)說(shuō)可以忽略不計(jì)。f(n)=o(g(n))，當(dāng)且僅當(dāng)f(n)=O(g(n)，但g(n)≠O(f(n))。例如：n是o(n2)的，等價(jià)於n是O(n2)，但n2≠O(n)。*證明當(dāng)n≥？時(shí)有2n＜n!證：由此可得：2n=o(n!)*

我們用f(n)﹤g(n)來(lái)表示f(n)是o(g(n))的。用該記號(hào)可簡(jiǎn)明地表示複雜性的層次。1﹤logn﹤n1/2﹤n﹤nlogn﹤n2﹤n3﹤2n﹤n!O 類似於 ≤Ω 類似於 ≥Θ 類似於 =o 類似於 <

不要將確切的關(guān)係和漸近符號(hào)相混淆。例如：

100n≥n 100n=O(n) n≤100n 100n=Ω(n) n≠100n 100n=Θ(n)

一般地，設(shè)f(n)=aknk+ak-1nk-1+…+a1n+a0，則f(n)=Θ(nk)，它蘊(yùn)含著f(n)=O(nk)，f(n)=Ω(nk)。*驗(yàn)證某數(shù)n是否是素?cái)?shù)演算法描述如下：

若均不能除盡，則n為素?cái)?shù)。只要有一個(gè)能除盡，則n為合數(shù)。為了提高效率，上述演算法可優(yōu)化如下：

原理：若存在一個(gè)數(shù)x（

≤x＜n），能整除n。設(shè)商為y，則有n=xy，顯然0<y≤

)且y能整除n。顯然檢查了y，就沒(méi)有必要再檢查x。*例1.16素?cái)?shù)測(cè)試的蠻力演算法演算法1.7演算法Brute-ForcePrimalityTest輸入：正整數(shù)n≥2輸出：若n是素?cái)?shù)，則輸出true，否則輸出false。1.s←

2.forj←2tosifj劃分sthenreturnfalseendforreturntrue

n的平方根可以在O(1)時(shí)間內(nèi)計(jì)算出。假設(shè)輸入是偶數(shù)，演算法僅僅執(zhí)行一次迴圈，所以演算法是Ω(1)的。若輸入是素?cái)?shù)，執(zhí)行迴圈次數(shù)為

，所以該演算法是O()的。演算法的時(shí)間複雜性不能用Θ來(lái)描述。*1.9空間複雜性空間複雜性定義（P19）為了求解問(wèn)題的實(shí)例，執(zhí)行計(jì)算步驟所需要的內(nèi)存空間的數(shù)目，它不包括分配用來(lái)存儲(chǔ)輸入的空間。換句話說(shuō)，僅僅是算法需要的工作空間。

空間複雜性的計(jì)算要比時(shí)間複雜性簡(jiǎn)單得多，可將時(shí)間複雜性的定義和符號(hào)移植到空間複雜性的表示。例1，在演算法LinearSearch中，僅需要一個(gè)記憶體單元保存搜索結(jié)果以及迴圈控制變數(shù)i、j，可以得出空間複雜性為Θ(1)。同理演算法BinarySearch、SelectionSort和InsertionSort。*例2：在演算法Merge中，需要和輸入大小相同的記憶體n個(gè)，因此空間複雜性為Θ(n)。同理演算法BottomUpSort。例3：輸出n個(gè)字元的所有排列只需要Θ(n)空間。如果需要保留這些排列用於後續(xù)計(jì)算，至少需要n!空間，即Ω

(n!)。許多問(wèn)題的處理需要在時(shí)間和空間之間平衡。一般來(lái)說(shuō)，給演算法分配的空間越大，演算法運(yùn)行速度就越快，反之亦然。迄今為止所討論的大多數(shù)演算法中，增加空間並不可能導(dǎo)致演算法速度的加快，有可能反而降低。但是，減小空間會(huì)導(dǎo)致演算法速度的降低是毫無(wú)疑問(wèn)的。*1.10最優(yōu)演算法

一般來(lái)說(shuō)，如果可以證明任何一個(gè)求解問(wèn)題Π的演算法必定是Ω(f(n))，那么我們把在O(f(n))時(shí)間內(nèi)求解問(wèn)題Π的任何演算法都稱為問(wèn)題Π的最優(yōu)演算法。任何基於比較的排序演算法，可以證明它的運(yùn)行時(shí)間必定是Ω(nlogn)。這就意味著：不能指望找到一個(gè)基于比較的排序算法，它的漸近運(yùn)行時(shí)間少于nlogn。因?yàn)檫@個(gè)理由，我們通常把時(shí)間複雜性為O(nlogn)的基於比較的排序演算法，稱為該問(wèn)題的最優(yōu)演算法。根據(jù)這一定義，演算法BottomUpSort是該問(wèn)題的最優(yōu)演算法．我們還稱，演算法BottomUpSort在常數(shù)因數(shù)範(fàn)圍內(nèi)是最優(yōu)的，以表示可能存在另一個(gè)基於比較的排序演算法，它的運(yùn)行時(shí)間是BottomUpSort演算法的執(zhí)行時(shí)間乘以一個(gè)常數(shù)因數(shù)。

演算法概述661.1 演算法與程式演算法：是滿足下述性質(zhì)的指令序列。輸入：有零個(gè)或多個(gè)外部量作為演算法的輸入。輸出：演算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成演算法的每條指令清晰、無(wú)歧義。有限性：演算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。程式：程式是演算法用某種程式設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程式可以不滿足演算法的性質(zhì)(4)即有限性。例如操作系統(tǒng)，是一個(gè)在無(wú)限迴圈中執(zhí)行的程式，因而不是一個(gè)演算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)副程式通過(guò)特定的演算法來(lái)實(shí)現(xiàn)。該副程式得到輸出結(jié)果後便終止。671.2 演算法與數(shù)據(jù)結(jié)構(gòu)描述演算法可以有多種方式自然語(yǔ)言方式、表格方式、圖示形式等本書(shū)將採(cǎi)用C++與自然語(yǔ)言相結(jié)合的方式演算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)係不了解施加於數(shù)據(jù)上的演算法就無(wú)法決定如何構(gòu)造數(shù)據(jù)，可以說(shuō)演算法是數(shù)據(jù)結(jié)構(gòu)的靈魂；反之演算法的結(jié)構(gòu)和選擇又常常在很大程度上依賴於數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)則是演算法的基礎(chǔ)。演算法＋數(shù)據(jù)結(jié)構(gòu)＝程式681.3 表達(dá)演算法的抽象機(jī)制從機(jī)器語(yǔ)言到高級(jí)語(yǔ)言的抽象高級(jí)程式設(shè)計(jì)語(yǔ)言的主要好處是：高級(jí)語(yǔ)言更接近演算法語(yǔ)言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時(shí)間的培訓(xùn)就可以勝任程式員的工作；高級(jí)語(yǔ)言為程式員提供了結(jié)構(gòu)化程式設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì)出來(lái)的程式可讀性好，可維護(hù)性強(qiáng)，可靠性高；高級(jí)語(yǔ)言不依賴於機(jī)器語(yǔ)言，與具體的電腦硬體關(guān)係不大，因而所寫(xiě)出來(lái)的程式可植性好、重用率高；把繁雜瑣碎的事務(wù)交給編譯程序，所以自動(dòng)化程度高，開(kāi)發(fā)週期短，程式員可以集中時(shí)間和精力從事更重要的創(chuàng)造性勞動(dòng)，提高程式品質(zhì)。691.3 表達(dá)演算法的抽象機(jī)制抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是演算法的一個(gè)數(shù)據(jù)模型連同定義在該模型上並作為演算法構(gòu)件的一組運(yùn)算。抽象數(shù)據(jù)類型帶給演算法設(shè)計(jì)的好處有：演算法頂層設(shè)計(jì)與底層實(shí)現(xiàn)分離；演算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)隔開(kāi)，允許數(shù)據(jù)結(jié)構(gòu)自由選擇；數(shù)據(jù)模型和該模型上的運(yùn)算統(tǒng)一在ADT中，便於空間和時(shí)間耗費(fèi)的折衷；用抽象數(shù)據(jù)類型表述的演算法具有很好的可維護(hù)性；演算法自然呈現(xiàn)模組化；為自頂向下逐步求精和模組化提供有效途徑和工具；演算法結(jié)構(gòu)清晰，層次分明，便於演算法正確性的證明和複雜性的分析。701.4 描述演算法與演算法設(shè)計(jì)描述演算法可以有多種方式，如自然語(yǔ)言方式、圖形表格方式等。在這裏，我們將採(cǎi)用C++語(yǔ)言來(lái)描述演算法。C++語(yǔ)言的優(yōu)點(diǎn)是類型豐富、語(yǔ)句精煉，具有面向?qū)ο蠛忘I向過(guò)程的雙重優(yōu)點(diǎn)。用C++來(lái)描述演算法可使整個(gè)演算法結(jié)構(gòu)緊湊、可讀性強(qiáng)。在課程中，有時(shí)為了更好地闡明演算法的思路，我們還採(cǎi)用C++與自然語(yǔ)言相結(jié)合的方式來(lái)描述演算法。演算法設(shè)計(jì)方法主要有：分治策略、動(dòng)態(tài)規(guī)劃、貪心演算法、回溯法、分支限界、概率演算法等，我們將在後面的章節(jié)中陸續(xù)介紹。711.4 描述演算法與演算法設(shè)計(jì)問(wèn)題求解(ProblemSolving)72證明正確性分析演算法設(shè)計(jì)程式理解問(wèn)題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)演算法設(shè)計(jì)策略設(shè)計(jì)演算法1.5演算法分析的基本原則正確性定義：在給定有效輸入後，演算法經(jīng)過(guò)有限時(shí)間的計(jì)算並產(chǎn)生正確的答案，就稱演算法是正確的。正確性證明的內(nèi)容：方法的正確性證明——演算法思路的正確性。證明一系列與演算法的工作對(duì)象有關(guān)的引理、定理以及公式。程式的正確性證明——證明所給出的一系列指令確實(shí)做了所要求的工作。程式正確性證明的方法：大型程式的正確性證明——可以將它分解為小的相互獨(dú)立的互不相交的模組，分別驗(yàn)證。小模組程式可以使用以下方法驗(yàn)證：數(shù)學(xué)歸納法、軟體形式方法等。731.5演算法分析的基本原則工作量——時(shí)間複雜性分析計(jì)量工作量的標(biāo)準(zhǔn):對(duì)於給定問(wèn)題，該演算法所執(zhí)行的基本運(yùn)算的次數(shù)?；具\(yùn)算的選擇：根據(jù)問(wèn)題選擇適當(dāng)?shù)幕具\(yùn)算。74問(wèn)題基本運(yùn)算在表中查找x比較實(shí)矩陣相乘實(shí)數(shù)乘法排序比較遍曆二叉樹(shù)置指針1.5演算法分析的基本原則佔(zhàn)用空間——空間複雜性分析兩種佔(zhàn)用：存儲(chǔ)程式和輸入數(shù)據(jù)的空間存儲(chǔ)中間結(jié)果或操作單元所佔(zhàn)用空間——額外空間影響空間的主要因素：存儲(chǔ)程式的空間一般是常數(shù)(和輸入規(guī)模無(wú)關(guān))輸入數(shù)據(jù)空間為輸入規(guī)模O(n)空間複雜性考慮的是額外空間的大小如果額外空間相對(duì)於輸入規(guī)模是常數(shù)，稱為原地工作的演算法。751.5演算法分析的基本原則簡(jiǎn)單性含義：演算法簡(jiǎn)單，程式結(jié)構(gòu)簡(jiǎn)單。好處：容易驗(yàn)證正確性便於程式調(diào)試簡(jiǎn)單的演算法效率不一定高。要在保證一定效率的前提下力求得到簡(jiǎn)單的演算法。761.5演算法分析的基本原則最優(yōu)性含義：指求解某類問(wèn)題中效率最高的演算法兩種最優(yōu)性最壞情況：設(shè)A是解某個(gè)問(wèn)題的演算法，如果在解這個(gè)問(wèn)題的演算法類中沒(méi)有其他演算法在最壞情況下的時(shí)間複雜性比A在最壞情況下的時(shí)間複雜性低，則稱A是解這個(gè)問(wèn)題在最壞情況下的最優(yōu)演算法。平均情況：設(shè)A是解某個(gè)問(wèn)題的演算法，如果在解這個(gè)問(wèn)題的演算法類中沒(méi)有其他演算法在平均情況下的時(shí)間複雜性比A在平均情況下的時(shí)間複雜性低，則稱A是解這個(gè)問(wèn)題在平均情況下的最優(yōu)演算法。尋找最優(yōu)演算法的途徑(以最壞情況下的最優(yōu)性為例)設(shè)計(jì)演算法A，求W(n)。相當(dāng)於對(duì)問(wèn)題給出最壞情況下的一個(gè)上界。尋找函數(shù)F(n)，使得對(duì)任何演算法都存在一個(gè)規(guī)模為n的輸入並且該演算法在這個(gè)輸入下至少要做F(n)次基本運(yùn)算。相當(dāng)於對(duì)問(wèn)題給出最壞情況下所需基本運(yùn)算次數(shù)的一個(gè)下界。如果W(n)=F(n)，則A是最優(yōu)的。如果W(n)>F(n)，A不是最優(yōu)的或者F(n)的下界過(guò)低。改進(jìn)A或設(shè)計(jì)新演算法A’使得W’(n)<W(n)。重新證明新下界F’(n)使得F’(n)>F(n)。重複以上兩步，最終得到W’(n)=F’(n)為止。771.5演算法分析的基本原則例：在n個(gè)不同的數(shù)中找最大的數(shù)?；具\(yùn)算：比較演算法：FindMax輸入：數(shù)組L，項(xiàng)數(shù)n11輸出：L中的最大項(xiàng)MAXMAX←L(1);i←2;whilei≤ndoifMAX<L(i)thenMAX←L(i);i←i+1;end。行3的比較進(jìn)行n－1次，故W(n)=n－1。定理：在n個(gè)數(shù)的數(shù)組中找最大的數(shù)，並以比較作為基本運(yùn)算的演算法類中的任何演算法最壞情況下至少要做n－1次比較。證：因?yàn)镸AX是唯一的，其他的n－1個(gè)數(shù)必須在比較後被淘汰。一次比較至多淘汰一個(gè)數(shù)，所以至少需要n－1次比較。結(jié)論：FindMax演算法是最優(yōu)演算法。781.6 演算法複雜性分析演算法複雜性是演算法運(yùn)行所需要的電腦資源的量，需要時(shí)間資源的量稱為時(shí)間複雜性，需要的空間資源的量稱為空間複雜性。這個(gè)量應(yīng)該只依賴於演算法要解的問(wèn)題的規(guī)模、演算法的輸入和演算法本身的函數(shù)。如果分別用N、I和A表示演算法要解問(wèn)題的規(guī)模、演算法的輸入和演算法本身，而且用C表示複雜性，那麼，應(yīng)該有C=F(N,I,A)。一般把時(shí)間複雜性和空間複雜性分開(kāi)，並分別用T和S來(lái)表示，則有：T=T(N,I)和S=S(N,I)。（通常，讓A隱含在複雜性函數(shù)名當(dāng)中）演算法複雜性=演算法所需要的電腦資源演算法的時(shí)間複雜性T(n)；演算法的空間複雜性S(n)。其中n是問(wèn)題的規(guī)模（輸入大?。?。791.6 演算法複雜性分析以上分別是最壞情況下、最好情況下和平均情況下的時(shí)間複雜性。其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N,I*)達(dá)到TMax(N)的合法輸入；I-是DN中使T(N,I-)達(dá)到TMin(N)的合法輸入；而P(I)是在演算法的應(yīng)用中出現(xiàn)輸入I的概率。801.6 演算法複雜性分析函數(shù)的漸進(jìn)性態(tài)與漸進(jìn)運(yùn)算式：一般來(lái)說(shuō)，當(dāng)N單調(diào)增加且趨於∞時(shí)，T(N)也將單調(diào)增加趨於∞。對(duì)於T(N)，如果存在函數(shù)T'(N)，使得當(dāng)N→∞使有(T(N)-T'(N))/T(N)→0，那麼我們就說(shuō)T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)性態(tài)。在數(shù)學(xué)上，T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)運(yùn)算式。例如：3N2+4NlogN+7與3N2。811.6 演算法複雜性分析演算法複雜性在漸近意義下的階：漸近意義下的記號(hào)：O、Ω、θ、o、ω設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。O的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有f(N)≤Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)=O(g(N))。即f(N)的階不高於g(N)的階。根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則：O(f)+O(g)=O(max(f,g))；O(f)+O(g)=O(f+g)；O(f)O(g)=O(fg)；如果g(N)=O(f(N))，則O(f)+O(g)=O(f)；O(Cf(N))=O(f(N))，其中C是一個(gè)正的常數(shù)；f=O(f)。821.6 演算法複雜性分析Ω的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有f(N)≥Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)下有界，且g(N)是它的一個(gè)下界，記為f(N)=Ω(g(N))。即f(N)的階不低於g(N)的階。θ的定義：定義f(N)=θ(g(N))當(dāng)且僅當(dāng)f(N)=O(g(N))且f(N)=Ω(g(N))。此時(shí)稱f(N)與g(N)同階。o的定義：對(duì)於任意給定的ε＞0，都存在正整數(shù)N0，使得當(dāng)N≥N0時(shí)有f(N)/Cg(N)＜ε,則稱函數(shù)f(N)當(dāng)N充分大時(shí)的階比g(N)低，記為f(N)=o(g(N))。例如，4NlogN+7=o(3N2+4NlogN+7)。

的定義：

(g(n))={f(n)|對(duì)於任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有n≥n0有：0≤cg(n)＜f(n)}等價(jià)於f(n)/g(n)

，asn。f(n)

(g(n))

g(n)

o(f(n))831.6 演算法複雜性分析漸近分析記號(hào)的若干性質(zhì)（1）傳遞性：f(n)=θ(g(n))，g(n)=θ(h(n))→f(n)=θ(h(n))；f(n)=Ｏ(g(n))，g(n)=Ｏ(h(n))→f(n)=Ｏ(h(n))；f(n)=Ω(g(n))，g(n)=Ω(h(n))→f(n)=Ω(h(n))；f(n)=ｏ(g(n))，g(n)=ｏ(h(n))→f(n)=ｏ(h(n))；f(n)=ω(g(n))，g(n)=ω(h(n))→f(n)=ω(h(n))；（2）反身性：f(n)=θ(f(n))；f(n)=Ｏ(f(n))；f(n)=Ω(f(n)).（3）對(duì)稱性：f(n)=θ(g(n))<==>g(n)=θ(f(n)).（4）互對(duì)稱性：f(n)=Ｏ(g(n))<==>g(n)=Ω(f(n))；f(n)=ｏ(g(n))<==>g(n)=ω(f(n))；（5）算術(shù)運(yùn)算：Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})；Ｏ(f(n))+Ｏ(g(n))=Ｏ(f(n)+g(n))；Ｏ(f(n))*Ｏ(g(n))=Ｏ(f(n)*g(n))；Ｏ(cf(n))=Ｏ(f(n))；g(n)=Ｏ(f(n))→Ｏ(f(n))+Ｏ(g(n))=Ｏ(f(n))。841.6 演算法複雜性分析規(guī)則Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})的證明：對(duì)於任意f1(n)∈Ｏ(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有n≥n1，有f1(n)≤c1f(n)。類似地，對(duì)於任意g1(n)∈Ｏ(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有n≥n2，有g(shù)1(n)≤c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對(duì)所有的n≥n3，有f1(n)+g1(n)≤c1f(n)+c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n))≤c32max{f(n),g(n)}＝2c3h(n)＝Ｏ(max{f(n),g(n)}).851.6 演算法複雜性分析取整函數(shù)

x：不大於x的最大整數(shù)；

x：不小於x的最小整數(shù)。取整函數(shù)的若干性質(zhì)x-1<xxx<x+1；

n/2+n/2=n;

對(duì)於n

0，a,b>0，有：

n/a/b=n/ab;

n/a/b=n/ab;

a/b(a+(b-1))/b;

a/b(a-(b-1))/b;其中，f(x)=x,g(x)=x

為單調(diào)遞增函數(shù)。861.6 演算法複雜性分析演算法分析中常見(jiàn)的複雜性函數(shù)871.6 演算法複雜性分析小規(guī)模數(shù)據(jù)複雜性增長(zhǎng)圖881.6 演算法複雜性分析中等規(guī)模數(shù)據(jù)複雜性增長(zhǎng)圖89小結(jié)程式與演算法漸進(jìn)運(yùn)算式程式複雜性習(xí)題：

90

遞歸與分治策略912.1遞歸的概念直接或間接地調(diào)用自身的演算法稱為遞歸演算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。在電腦演算法設(shè)計(jì)與分析中，使用遞歸技術(shù)往往使函數(shù)的定義和演算法的描述簡(jiǎn)潔且易於理解。下麵來(lái)看幾個(gè)實(shí)例。922.1遞歸的概念例1階乘函數(shù)可遞歸地定義為：其中：n=0時(shí)，n!=1為邊界條件n>0時(shí)，n!=n(n-1)!為遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算後得出結(jié)果。932.1遞歸的概念例2Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，…，被稱為Fibonacci數(shù)列。它可以遞歸地定義為：第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：publicstaticintfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}94小兔子問(wèn)題2.1遞歸的概念例3Ackerman函數(shù)當(dāng)一個(gè)函數(shù)及它的一個(gè)變數(shù)是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：前2例中的函數(shù)都可以找到相應(yīng)的非遞歸方式定義。但本例中的Ackerman函數(shù)卻無(wú)法找到非遞歸的定義。952.1遞歸的概念A(yù)(n，m)的引數(shù)m的每一個(gè)值都定義了一個(gè)單變數(shù)函數(shù)：M=0時(shí)，A(n,0)=n+2M=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2^n。M=3時(shí)，類似的可以推出M=4時(shí)，A(n,4)的增長(zhǎng)速度非?？欤灾领稕](méi)有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一函數(shù)。定義單變數(shù)的Ackerman函數(shù)A(n)為，A(n)=A(n，n)。定義其擬逆函數(shù)α(n)為：α(n)=min{k｜A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。α(n)在複雜度分析中常遇到。對(duì)於通常所見(jiàn)到的正整數(shù)n，有α(n)≤4。但在理論上α(n)沒(méi)有上界，隨著n的增加，它以難以想像的慢速度趨向正無(wú)窮大。962.1遞歸的概念例4排列問(wèn)題設(shè)計(jì)一個(gè)遞歸演算法生成n個(gè)元素{r1,r2,…,rn}的全排列。設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個(gè)元素，Ri=R-{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上首碼得到的排列。R的全排列可歸納定義如下：當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素；當(dāng)n>1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)構(gòu)成。972.1遞歸的概念例5整數(shù)劃分問(wèn)題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。例如正整數(shù)6有如下11種不同的劃分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。982.1遞歸的概念前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)係，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)係，因此考慮增加一個(gè)引數(shù)：將最大加數(shù)n1不大於m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)係：q(n,1)=1，n≥1；當(dāng)最大數(shù)n1不大於1時(shí)，任何正整數(shù)n只有一種劃分形式：n=1+1+...+1(共n個(gè))。Q(n,m)=q(n,n)，m≥n；最大加數(shù)n1實(shí)際上不能大於n。因此，q(1,m)=1。q(n,n)=1+q(n,n-1)；正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。q(n,m)=q(n,m-1)+q(n-m,m),n>m>1；正整數(shù)n的最大加數(shù)n1不大於m的劃分由n1=m的劃分和n1≤m-1的劃分組成。992.1遞歸的概念正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。1002.1遞歸的概念例6Hanoi塔問(wèn)題設(shè)a,b,c是3個(gè)塔座。開(kāi)始時(shí)，在塔座a上有一疊共n個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤(pán)移到塔座b上，並仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：每次只能移動(dòng)1個(gè)圓盤(pán)；任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤(pán)移至a,b,c中任一塔座上。publicstaticvoidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}思考：如果塔的個(gè)數(shù)變?yōu)閍,b,c,d四個(gè)，現(xiàn)要將n個(gè)圓盤(pán)從a全部移動(dòng)到d，移動(dòng)規(guī)則不變，求移動(dòng)步數(shù)最小的方案。1012.1遞歸的概念遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明演算法的正確性，因此它為設(shè)計(jì)演算法、調(diào)試程式帶來(lái)很大方便。缺點(diǎn)：遞歸演算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是佔(zhàn)用的存儲(chǔ)空間都比非遞歸演算法要多。解決方法：在遞歸演算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸演算法。採(cǎi)用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。通過(guò)Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。後兩種方法在時(shí)空複雜度上均有較大改善，但其適用範(fàn)圍有限。1022.2分治法的基本思想分治法的基本思想分治法的基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同。對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。將求出的小規(guī)模的問(wèn)題的解合併為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。103凡治眾如治寡，分?jǐn)?shù)是也?！獙O子兵法2.2分治法的基本思想104nT(n/2)T(n/2