1、第十章 算法分析與設計,讀者在學習以前各章的基礎上，系統(tǒng)地閱讀本章，可對算法的設計和分析技術有一個鳥瞰，以便于將本書所學到的算法歸類整理，達到開闊思路，提高觀點，增強興趣的目的。,目錄,10.1算法分析技術 10.1.1空間代價分析 10.1.2時間代價分析 10.2算法設計技術 10.2.1分治法 10.2.2貪心法 10.2.3動態(tài)規(guī)劃法 10.2.4回溯法 10.2.5分枝界限法與0/1背包問題*,10.1 算法分析技術,評價一個算法的代價，主要看執(zhí)行算法時所需要占用的計算機空間的大小和計算過程需要花費的計算機CPU時間的多少。 算法的分析主要包含時間和空間兩個方面。,10.1.1 空間

2、代價分析,根據算法執(zhí)行過程中對存儲空間的使用方式，可以把對算法空間代價分析分成兩種：靜態(tài)分析和動態(tài)分析。,一個算法靜態(tài)使用的存儲空間，稱為靜態(tài)空間。 靜態(tài)分析的方法比較容易，只要求出算法中使用的所有變量的空間，再折合成多少空間存儲單位即可。,靜態(tài)分析,例10.1直接插入排序的空間代價分析（參看算法8.1） 被排序的記錄的個數決定了問題的規(guī)模。 被排序的對象在調用函數中申請，并用一個指針變量pvector傳遞給被調函數，空間大小顯然是O(n)； 在排序程序中，算法以靜態(tài)方式定義了兩個整型變量i和j、一個存儲插入元素的臨時變量temp，所以在算法中分配的空間為一個 常量，記為O(1)（對于常量c而

3、言，O(c)與O(1)為相同復雜度）。,動態(tài)分析 一個算法在執(zhí)行過程中，必須以動態(tài)方式分配的存儲空間是指在算法執(zhí)行過程中才能分配的空間稱為動態(tài)空間。 動態(tài)空間的確定主要由兩種情況構成： （1）函數的遞歸； （2）執(zhí)行動態(tài)分配函數。,對于遞歸函數而言，由于每次調用需要分配不同的運行空間，所以遞歸函數的空間代價，不能簡單地采用靜態(tài)分析方法。 假設靜態(tài)分析一個遞歸函數的空間代價為一個常量c，如果遞歸深度為（h的大小依賴于程序的動態(tài)執(zhí)行），動態(tài)空間代價應該為C*h。,函數的遞歸調用,例10.2 快速排序（參看算法8.8） 對函數靜態(tài)分析的空間與待排序記錄的個數無關，為一常量。遞歸深度最大等于，這時動態(tài)

4、空間代價為O(n)；若每次都選較短的部分先處理，則遞歸深度不會超過log2n，這時動態(tài)空間代價即為O(log2n)。,一個函數（或過程）如果使用了malloc和free函數，malloc和free所開辟、釋放的空間只能在算法執(zhí)行過程中加以確定，這些空間屬于動態(tài)空間。 下面的討論中，假設每次分配的空間與問題規(guī)模無關，只是一個常數C。,執(zhí)行動態(tài)分配函數,沒有使用free函數 動態(tài)空間代價為O(k)，k為使用malloc的次數（包括在循環(huán)和遞歸調用中動態(tài)執(zhí)行的次數）。,分如下兩種情況討論：,使用free函數 設free使用次數為j。 令：0， pi（i=1.j）為第i-1次使用free和次使用fre

5、e之間 執(zhí)行malloc的次數。 用公式i=i-1+ p i-1 可以計算出在第i-1次使用free和第i次使用free（i=1.j）之間使用的最大動態(tài)空間數。 再定義j如下： 于是整個算法使用的動態(tài)空間代價為：,例10.3 一個算法執(zhí)行過程中malloc和free順序為（代表malloc，代表free）。 , jj 0 =， 1， 2， 3， 4， 5， 6， 7。,10.1.2 時間代價分析,算法的執(zhí)行時間絕大部分花在循環(huán)和遞歸上。,循環(huán) 循環(huán)語句的時間代價一般用以下三條原則分析： （）對于一個循環(huán)，循環(huán)次數乘以每次執(zhí)行簡單語句的數目即為其時間代價。 （）對于多個并列循環(huán)，可先計算每個循環(huán)

6、的時間代價，然后按大表示法的加法規(guī)則計算總代價。 （） 對于多層嵌套循環(huán)，一般可按大表示法的乘法規(guī)則計算。但如果嵌套是有條件的，為精確計算其時間代價，要仔細累加循環(huán)中簡單語句的實際執(zhí)行數目，以確定其時間代價。,例10.5求帶權圖中每一對結點之間的最短路徑的算法的時間代價（參看算法9.7）。解 問題規(guī)模：帶權圖頂點數目為。算法中共有五個循環(huán)，前兩個循環(huán)與后三個是并列關系。前兩個循環(huán)是嵌套關系，后三個之間也是嵌套關系。,最內層循環(huán)的時間代價為一常數C， 則前兩個循環(huán)時間代價為： 后三個循環(huán)時間代價為： 所以總的時間代價為O(n3)。,例10.6 為實現無回溯的匹配，而要計算模式串的NEXT數組算法

7、的時間代價（參看算法3.8）。,問題規(guī)模：模式串長度。 從形式上來看，這是一個二重循環(huán)，每重循環(huán)最多執(zhí)行m次，最大運行時間可能達到O(m2)。 仔細分析：因為每執(zhí)行一次外層（第4行）循環(huán)，i嚴格增1（第6行），所以外層循環(huán)正好執(zhí)行m1次；但是，k的值從（第2行）-1開始，k+恰好執(zhí)行（第6行）m1次，并且只有在這一語句中k被增值。而在內層循環(huán)（第5行）中，語句knextk至少使k減少1，整個算法中，這個語句的執(zhí)行次數累計起來不可能超過m1次（否則，k將小于-1，這是不可能的），所以內層循環(huán)總的執(zhí)行次數最大為m1。 因此算法3.8的執(zhí)行時間為O(m)。,遞歸對于遞歸算法，一般可把時間代價表示為一

8、個遞歸方程。解這種遞歸方程最常用的方法是進行遞歸擴展，通過層層遞歸，直到遞歸出口，然后再進行化簡。,例如，有某遞歸算法，當n=1時是遞歸出口，執(zhí)行的時間是一個常量；當n1時，可以把問題分解成a（a=1）個子問題的遞歸計算，每個子問題的規(guī)模是原來問題的b(b=1)分之一；分解問題和合并子問題解的花費為d(n)。整個問題的時間代價可以表示為下面一類遞歸方程的計算：,遞歸擴展過程如下：,設k，則 又設d(x)為“積性函數”： d(x*y)=d(x)*d(y),則有：,以下分三種情況討論：,（1）d(b)，則,（2）d(b)，則,（3）d(b)，則,例10.8求快速排序法的時間代價。 此算法的遞歸方程

9、可表示為：T(n)T(n/2)n，這里，d(x)是積性函數。因為d(b)，所以 結論與8.4節(jié)所得結果一樣。,10.2 算法設計技術 10.2.1分治法,分治法(Divide and Conquer)是把一個規(guī)模為的問題分成兩個或多個較小的與原問題類型相同的子問題，通過對子問題的求解，并把子問題的解合并起來從而構造出整個問題的解，即對問題分而治之。 如果子問題的規(guī)模仍然相當大，可以對此子問題重復地應用分治策略。,分治法的算法框架 return_type d_and_c( objArray * p , int i , int j ) int temp ; if ( simple (p,i,j)

10、) return solve (p,i,j) ; /*基值處理 */ temp = divide (p,i,j) ; /*分解問題 */ return ( combine ( d_and_c(p,i,temp-1) , d_and_c(p,temp,j) ) ); /*遞歸調用與合并處理 */ ,例子,二分法檢索就是我們所學過的應用分治策略的典型的例子。 快速排序算法，歸并排序算法、梵塔問題等都可以用分治策略求解。 快速排序算法每趟把一個元素放入排完序后它所應在的位置，這個位置把原表分成了兩個宏觀有序的子表； 歸并排序算法是把規(guī)模為的問題分成規(guī)模為n/2的兩個子問題； 而梵塔問題分原問題為兩個

11、規(guī)模為n-1的子問題。,討論,分治策略把問題分成若干個子問題，分成的子問題的數目一般不大。 如果每次分成的各子問題的規(guī)模相等或近乎相等的話，則分治策略的效率較高，否則效率就比較低。 例如：直接插入排序（算法8.1）可以看作是把原問題分解成兩個子問題，一個是規(guī)模為的問題，另一個是規(guī)模為n-1的問題，算法的時間代價是O(n)級的。 而歸并排序把原問題分成了兩個大小為n/2的問題，算法的時間代價是O(nlog2n)級的。,10.2.2貪心法,求著色問題近似解的貪心法(greedy) 其基本思想為：先用一種顏色給盡可能多的結點上色，然后再用另一種顏色在未著色的結點中給盡可能多的結點上色，如此反復直到所

12、有結點都被著色為止。,Dijkstra的最短路徑算法 求從源點到其它各結點的最短路徑 它總是從那些最短路徑還不知道的結點中挑選一個到源點最近的結點。 另一采用貪心策略的算法是Kruskal的求最小生成樹算法,背包問題：給定個物體和一個背包，已知物體的重量為i，價值為pi，背包能容納物體的重量為。要求確定一組分數i（i），能夠把物體的i部分放入背包，使得 最大（即將盡量多的價值裝入背包）。,因為： p/w25/181.38， p/w24/151.6， p3/w315/101.5， p/wp/wp/w。 所以首先把物品2全部放入背包，然后考慮物品3，最后如果還有余地考慮物品1。這樣得到的結果為（x

13、，x2，x3）（0，1，1/2），,例如：3，20， (p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10),解背包問題的貪心算法的實現： 其中參數數組p和w中,按pi/wi的降序分別存放物體的價格和重量；m是背包能放的物體總重量，n是物體件數。x存放解向量。 float knapSack(float* p, float* w, float * x ,float m, int n) int i=0;float s=0; while(i0 ) s += pi*m/wi; xi = m/wi; i+; for ( ; in ; i+ ) xi=0; return

14、(s); ,討論,貪心法在各個階段，選擇那些在某些意義下是局部最優(yōu)的方案，但不是每次都能成功地產生出一個整體最優(yōu)解。 仍然以著色問題為例，如果要著色的圖如圖10.1所示，采用貪心法，并且按a、b、c、d、e的順序處理，得到的結果則需要三種不同的顏色：第一種顏色著a和b，第二種顏色著c和d，剩下的e還需要一種顏色才行。 對某些問題，如果只要求得一個與最優(yōu)解相差不多的次優(yōu)解就滿足要求時，選用貪心法可以幫助我們很快地得到這樣的解。,10.2.3 動態(tài)規(guī)劃法,有些問題常常在分解時會產生大量的子問題，同時子問題界限不清，互相交叉，因而可能重復多次解同一個子問題。 解決這種重復的方法：可以在得到每個子問題

15、的解（包括其子子問題的解）時，把解保留在一個表格中，遇到相同的子問題時，就從表中找出來直接使用。這種方法就是動態(tài)規(guī)劃法（Dynamic Programming）。,例10.10求組合數。我們知道組合數有這樣的一個遞推式： 每次求解可將其分為兩個子問題和。把 按遞推式分解得到圖10.2的二叉樹結構。,例子,本書所見過的運用動態(tài)規(guī)劃法的算法有： 所有結點間的最短路徑算法 最佳二叉排序樹的構造算法。 例10.10求組合數組合數有下面的遞推式：,把,按遞推式分解 得到的二叉樹結構。,首先，將的位置上以及0的位置上元素皆填為1。填某一中間表目時，只要把它右邊表目的元素與右下方表目的元素之和填入即可。這樣

16、，很快就能求出 10。,計算組合數的動態(tài)規(guī)劃算法： int combinat(int m,int n) int i,j; int mat10001000; if(n=0|m=n)return 1; for(j=0;jn;j+) mat0j=1; for(i=1;i=m-n;i+) if (j=0) matij=i+1; elsematij=mati-1j+matij-1; /* 計算Cmn */ return (matm-nn-1); /* 返回計算的結果 */ ,問題的規(guī)模越大，用動態(tài)規(guī)劃法的好處就越明顯地體現出來。填完整個表，得到題目所求，花的時間要大大快于不填表遞歸的求解所花的時間。 設

17、題目的規(guī)模為，分治法時間代價是O(2n)，而動態(tài)規(guī)劃法的時間代價僅要O(n2)。 因此，在解這類問題時，一般采用動態(tài)規(guī)劃法。,動態(tài)規(guī)劃法的好處,區(qū)別1 動態(tài)規(guī)劃法先求子問題的解，然后通過求解子問題構造原問題的解； 而貪心算法是直接地解原問題。 區(qū)別2 動態(tài)規(guī)劃法通過對若干局部最優(yōu)解的比較，去掉了次優(yōu)解，從而產生了更高一層次的局部最優(yōu)解。相當于對較低層次的局部最優(yōu)解進行貪心的選擇而得到高一級的局部最優(yōu)解，因而最終產生一個最高層次的局部最優(yōu)解。 而貪心法每階段只作一個挑選，各階段的解一經選出就固定不變了，后階段的局部最優(yōu)是基于前階段的挑選，所以往往只能求出次優(yōu)解。,動態(tài)規(guī)劃法與貪心法的區(qū)別,動態(tài)規(guī)

18、劃法與分治法的比較,共同點是:把一個大問題分解為若干較小的子問題，通過求解子問題而得到原問題的解。 不同點是： 分治法每次分解的子問題數目比較少，子問題之間界限清楚，處理的過程通常是自頂向下進行； 動態(tài)規(guī)劃法分解的子問題可能比較多，而且子問題相互包含，為了重用已經計算的結果，要把計算的中間結果全部保存起來，通常是自底向上進行。,10.2.4 回溯法,有一類問題，要求找到一個滿足某些條件的最優(yōu)解，如果進行徹底的搜索，要進行大量的比較，要以大量的運算時間為代價。 回溯法（backtracking）求助于回溯技巧，常?？梢源蟠蟮販p少實際的搜索數目。,例子,第4章中給出的求解迷宮問題的算法4.11，采

19、用的就是典型的回溯方法， 另外關于深度優(yōu)先對樹、二叉樹和圖的周游算法中也直接采用了回溯的思想。,由于回溯方法的本質是用深度優(yōu)先的方法在解的空間樹中搜索。所以在算法中都需要建立一個棧，用來保存搜索的路徑。一旦產生的部分解序列不合要求，就要從棧中找到回溯的前一個位置，繼續(xù)試探。,一般回溯方法的程序結構： void backtrack (void) 準備初值； do while (范圍未超界并且工作未完成) 分析條件；/* 保證滿足條件才往下去 */ if (成功) 路徑進棧； 由第一選擇開始進入下一層；/* 縱向走 */ else 本層更換選擇； /* 橫向走 */ if ( 工作未完成 ) 彈出

20、堆棧； 原來的上一層更換為下一選擇；/* 回溯到上層橫向*/ while ( 全部工作未完成 ) ； 輸出結果； ,給定圖10.6，其中，標明七個區(qū)域，要求用不多于四種顏色對這七個區(qū)域進行著色，使得有公共界的區(qū)域不同色（就象世界地圖上，相鄰的國家著不同的顏色一樣）。,例10.12四色問題：,回溯法：按區(qū)域編號從小到大順序著色。按色數從小到大的順序進行試探。如試探成功，則對下一區(qū)域著色；如不成功，則用本區(qū)域的色數加再試探；如果色數大于，則退回上一區(qū)域，改色（已著的顏色的色數加）再試探。 需要注意的是：按照順序進行試探，這是至關重要的，它保證了搜索的系統(tǒng)性和徹底性。,存儲表示：為了用程序實現這個算

21、法，可以先把所給的問題化為下列無向圖的形式,圖中每一個頂點對應一個區(qū)域，區(qū)域有公共邊界表現為相應頂點間有邊連接。再選擇適當的數據結構（例如用相鄰矩陣表示圖）就可以實現這個算法。,應用回溯方法解問題時，這問題的解須能表示為一個元組?；厮莘椒ㄍㄟ^系統(tǒng)的搜索來確定出問題的解。 四色問題的解含于（，）到（，）之間的七元組中(可以用樹形結構來表示這些元組)。我們可以構造出一棵解空間樹：它是一棵高度為7的四叉完全樹，共有47個葉子。解問題就相當于用一種方法周游這棵樹，從樹根到樹葉之間的路徑就是一個元組（一個后選的解）。,解空間樹,窮舉測試是對所有的葉子都一一測試，而回溯的方法是從樹根開始，邊試探邊往下走，

22、若在某一層次查明不符合題意，則不往下走，砍掉以下的樹杈，跳到下一杈上繼續(xù)試探著往下走。這樣邊走邊砍，砍掉大量的樹杈，從而省掉大量測試。一旦走到葉子，就找到了一組解。,回溯與剪枝,四色問題的搜索樹,10.2.5 分枝界限法與0/1背包問題,分枝界限法（branch and bound）也是一種在表示問題解空間的樹上進行系統(tǒng)搜索的方法。所不同的是，回溯法使用了深度優(yōu)先策略，而分枝界限法一般采用廣度優(yōu)先策略，同時還采用最大收益（或最小損耗）策略來控制搜索的分枝。,假設給定n個物體和一個背包，物體i的重量為wi，價值為pi（i=1,2,n），背包能容納的物體重量為m，要從這n個物體中選出若干件放入背包

23、，使得放入物體的總重量小于等于m，而總價值達到最大。,0/1背包問題,如果用xi=1表示將第i件物體放入背包，用xi=0表示未放入，則問題變?yōu)檫x擇一組xi 使得 與例10.9的背包問題相比，這里的xi只能取0或1兩種值，所以稱為0/1背包問題。,例10.14 0/1背包,一個具體的0/1背包實例： 已知n=4, m=15, w=(2,4,6,9), p=(10,10,12,18) 求解x=(x1,x2,x3,x4)，（xi=0,1），使得,在圖10.10中把本題所有可能的解用一棵高度為4的完全二叉樹表示出來。 圖中給每個結點的圓圈內加上一個數字作為結點的標記； 結點的附近標有一個與當前位置對應

24、的x值，形式為（x1,x2,x3,x4），其中xi=?表示xi的取值尚未確定； 每個結點的附近還有一對用括起來的數字，其中第一個數字表示當前位置已放入背包的物體重量，后面的數字表示當前位置已放入物品的價值。,0/1背包問題的解空間樹,在符合條件的解中，結點29的wp=38是最大值，x的值為（1，1，0，1），是最優(yōu)解。 由于x的取值個數隨物體個數n按2n速度增長，所以求出所有的可行解再選取最優(yōu)解的時間代價太大。,為了提高求解的效率，我們很容易想到上一節(jié)介紹的回溯法，通過回溯可以刪除不必要的分枝。,但是，遺憾的是，對本例而言，只有葉結點23，27，31可以忽略，因此改進不大。 回溯算法的另一個缺

25、點是：在搜索過程中即使找到了最優(yōu)解也不能馬上確定它就是最優(yōu)的，只有把它所有的可行解全都求出來以后才能確定最優(yōu)解。,這種方法對樹中的每個結點定義了一對界，分別給出沿著該結點繼續(xù)搜索可能得到的解的收益上界（用u表示）和收益下界（用l表示）。這兩個值給得越精確，剪枝的控制就越有效。,分枝界限法在剪枝的技術方面 增加了智能的成分,假如0/1背包問題的最優(yōu)解已經求出，解的px值一定不能超過用一般的（算法10.2所求的背包問題的）最優(yōu)解的價值。 因此我們就可以用相同條件的由貪心法求出的背包問題解的價值，作為這里0/1背包最優(yōu)解收益的上界。,以背包問題為例， 來說明如何求出每個結點的u值。,0/1背包問題的

26、收益的下界可以選用它自己的任何一個可行解的收益作初值。 我們不妨把它就取成：由算法10.2求出的收益上界減去求解過程中最后放入背包的xi1的物品的相應部分價值。它顯然一定是這個0/1背包問題的一個可行解。,以背包問題為例， 來說明如何求出每個結點的l值。,用以上方法求出背包問題的上/下界，作為圖10.9中根結點的u(1)和l(1)值為： u(1)=38 (對應于算法10.2的解為x=(1,1,1,1/3) ) l(1)=32 （對應于0/1背包問題的可行解為x=(1,1,1,0) ） 然后用同樣的思想對圖中每個結點都可以求出各自的u, l值。,分枝界限法的關鍵在于：可以利用求出的各個結點的收益上/下界，有效地實現剪枝。,例如，通過上面對結點2和3的計算結果，可以知道，沿結點2繼續(xù)搜索最好的結果是得到32的收益，但是如果沿結點3繼續(xù)的話，至少可以保證32的收益。因此如果我們只希望找到一個最優(yōu)解的話，就可以把以2為根的子樹全部剪掉。 注意，這一剪枝，把整個問題求解的空間砍去一半！,根據以上的思路可以剪掉很多分支，達到加快搜索的目的。具體的剪枝和搜索過程請參見教材。,在使用分枝界限法搜索解的空間時，從根結點出發(fā)，每個結點最多處理一次，在生成當前結點的子結點時，把所有符合題目要求（wxm）并且在已知界值之內的結點放在一