二章算法設計與分析的基本方法及技巧ppt課件

1、算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 1國家示范性軟件學院 http:/ 2006 秋第二章算法設計與分析的根本方法及技巧2.1 程序運轉(zhuǎn)時間2.2 一類遞歸方程的求解2.3 分治2.4 平衡2.5 貪婪法2.6 動態(tài)規(guī)那么2.7 回溯算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 2國家示范性軟件學院 http:/ 2006 秋算法算法Algorithm：是對特定問題求解步驟的一種描畫，它是：是對特定問題求解步驟的一種描畫，它是指令規(guī)那么的有限序列，其中每一條指令表示一個或多個操作。指令規(guī)那么的有限序列，其中每一條指令表示一個或多個操作。算法是在有限步驟內(nèi)求解某一問題所運用的一組定義明確的規(guī)那么。

2、通俗點說,就是計算機解題的過程。在這個過程中，無論是構(gòu)成解題思緒還是編寫程序,都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。Persian Textbook()的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm 約公元前825年從字面上看，這個名字的意思是“Jafar 的父親，Mohammed 和 Ms 的兒子，Khowrizm 的本地人。Khowrizm 是前蘇聯(lián)XBA(基發(fā)) 的小城鎮(zhèn) 。Al-Khowrizm 寫了著名的書Kitab al jabr wal-muqabala ()；算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 3國家示范性軟

3、件學院 http:/ 2006 秋資料：資料：AlgorithmAlgorithm與與LogarithmLogarithm這個詞不斷到這個詞不斷到19571957年之前在年之前在Websters New World Dictionary(Websters New World Dictionary()中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老方式的中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老方式的“AlgorismAlgorism( (算術(shù)算術(shù)) )，指的是用阿拉伯數(shù)字進展算術(shù)運算的過程。在中世紀時，珠算家，指的是用阿拉伯數(shù)字進展算術(shù)運算的過程。在中世紀時，珠算家用算盤進展計算，而算術(shù)家用

4、算術(shù)進展計算。中世紀之后，對這個詞的來源用算盤進展計算，而算術(shù)家用算術(shù)進展計算。中世紀之后，對這個詞的來源曾經(jīng)拿不準了，早期的言語學家試圖推斷它的來歷，以為它是從把曾經(jīng)拿不準了，早期的言語學家試圖推斷它的來歷，以為它是從把algiros(algiros(費力的費力的)+arithmos()+arithmos(數(shù)字數(shù)字) )組合起來派生而成的，但另一些人那么不組合起來派生而成的，但另一些人那么不贊同這種說法，以為這個詞是從贊同這種說法，以為這個詞是從“喀斯迪爾國王喀斯迪爾國王AlgorAlgor派生而來的。最后，派生而來的。最后，數(shù)學史學家發(fā)現(xiàn)了數(shù)學史學家發(fā)現(xiàn)了algorism(algorism

5、(算術(shù)算術(shù)) )一詞的真實來源：它來源于著名的一詞的真實來源：它來源于著名的Persian Persian Textbook(Textbook()的作者的名字的作者的名字Abu Jafar Mohammed ibn Ms al-Abu Jafar Mohammed ibn Ms al-Khowrizm Khowrizm 約公元前約公元前825825年年從字面上看，這個名字的意思是從字面上看，這個名字的意思是“Jafar Jafar 的父親，的父親，Mohammed Mohammed 和和 Ms Ms 的兒子，的兒子，Khowrizm Khowrizm 的本地人。的本地人。Khowrizm Kh

6、owrizm 是是前蘇聯(lián)前蘇聯(lián)XBA(XBA(基發(fā)基發(fā)) ) 的小城鎮(zhèn)的小城鎮(zhèn) 。Al-Khowrizm Al-Khowrizm 寫了著名的書寫了著名的書Kitab al jabr Kitab al jabr wal-muqabala (wal-muqabala ()；另一個詞，；另一個詞，“algebraalgebra( (代數(shù)代數(shù)) )，是從他的書的標題引出來的，雖然這本書實踐上根本不是講代數(shù)的。是從他的書的標題引出來的，雖然這本書實踐上根本不是講代數(shù)的。逐漸地，逐漸地，“algorismalgorism的方式和意義就變得面目全非了。如牛津英語字典所闡的方式和意義就變得面目全非了。如牛津英

7、語字典所闡明的，這個詞是由于同明的，這個詞是由于同arithmetic(arithmetic(算術(shù)算術(shù)) )相混淆而構(gòu)成的錯拼詞。由相混淆而構(gòu)成的錯拼詞。由algorismalgorism又變成又變成algorithmalgorithm。一本早期的德文數(shù)學詞典。一本早期的德文數(shù)學詞典 Vollstandiges Vollstandiges Mathematisches Lexicon (Mathematisches Lexicon () ) ，給出了，給出了Algorithmus (Algorithmus (算法算法) )一詞的如下定義：一詞的如下定義：“在這個稱號之下，組合了四種類型的算術(shù)計

8、算的概念，即在這個稱號之下，組合了四種類型的算術(shù)計算的概念，即加法、乘法、減法、除法。拉頂短語加法、乘法、減法、除法。拉頂短語algorithmus infinitesimalis (algorithmus infinitesimalis (無限無限小方法小方法) ) ，在當時就用來表示，在當時就用來表示Leibnitz(Leibnitz(萊布尼茲萊布尼茲) )所發(fā)明的以無限小量進展所發(fā)明的以無限小量進展計算的微積分方法。計算的微積分方法。19501950年左右，年左右，algorithmalgorithm一詞經(jīng)常地同歐幾里德算法一詞經(jīng)常地同歐幾里德算法(Euclids algorithm)(

9、Euclids algorithm)聯(lián)聯(lián)絡在一同。這個算法就是在歐幾里德的絡在一同。這個算法就是在歐幾里德的 (Euclids Elements ,(Euclids Elements ,第第VIIVII卷，命題卷，命題i i和和ii)ii)中所論述的求兩個數(shù)的最大公約數(shù)的過程中所論述的求兩個數(shù)的最大公約數(shù)的過程( (即輾轉(zhuǎn)相除法即輾轉(zhuǎn)相除法) )。算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 4國家示范性軟件學院 http:/ 2006 秋遞歸技術(shù) 最常用的算法設計思想，表達于許多優(yōu)秀算法之中 分治法 分而制之的算法思想，表達了一分為二的哲學思想 模擬法 用計算機模擬實踐場景，經(jīng)常用于與概率有關的問

10、題 貪婪算法 采用貪婪戰(zhàn)略的算法設計 形狀空間搜索法 被稱為“萬能算法的算法設計戰(zhàn)略 隨機算法 利用隨機選擇自順應地決議優(yōu)先搜索的方向 動態(tài)規(guī)劃 常用的最優(yōu)化問題處理方法 “好的算法的規(guī)范：好的算法的規(guī)范： 正確性，算法能滿足詳細問題的需求正確性，算法能滿足詳細問題的需求 可讀性，首先方便閱讀與交流，其次才是機器執(zhí)行可讀性，首先方便閱讀與交流，其次才是機器執(zhí)行 強壯性，輸入錯誤時，能作出反響，防止異常出錯強壯性，輸入錯誤時，能作出反響，防止異常出錯 效率與低存儲量要求效率與低存儲量要求算法的特征：算法的特征： 有窮性、確定性、輸入、輸出、能行性有窮性、確定性、輸入、輸出、能行性算法與數(shù)據(jù)結(jié)構(gòu)

11、Slides. 2 - 5國家示范性軟件學院 http:/ 2006 秋對算法對算法“正確性的要求：正確性的要求： 不含語法錯誤；不含語法錯誤； 對于幾組輸入數(shù)據(jù)能得到滿足要求的結(jié)果；對于幾組輸入數(shù)據(jù)能得到滿足要求的結(jié)果； 對精心選擇苛刻并帶有刁難的數(shù)據(jù)能得到滿足要求的結(jié)果；對精心選擇苛刻并帶有刁難的數(shù)據(jù)能得到滿足要求的結(jié)果； 對于一切合法的輸入均得到滿足要求的結(jié)果；對于一切合法的輸入均得到滿足要求的結(jié)果；算法描畫：算法描畫： 自然言語；程序設計言語；類言語自然言語；程序設計言語；類言語*；關于本書采用的類言語描畫：關于本書采用的類言語描畫： 構(gòu)造類型闡明構(gòu)造類型闡明 輸入輸出商定輸入輸出商定

12、( cin v , cout v ) new 和和 delete 引入援用類型引入援用類型 其他其他算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 6國家示范性軟件學院 http:/ 2006 秋影響算法執(zhí)行的要素：影響算法執(zhí)行的要素： 算法實現(xiàn)后所耗費的時間算法實現(xiàn)后所耗費的時間* 算法實現(xiàn)后所占存儲空間的大小算法實現(xiàn)后所占存儲空間的大小* 算法能否易讀、易移植等等其它問題算法能否易讀、易移植等等其它問題影響時間特性的四個要素：影響時間特性的四個要素： 程序運轉(zhuǎn)時輸入數(shù)據(jù)的總量程序運轉(zhuǎn)時輸入數(shù)據(jù)的總量 對源程序編譯所需的時間對源程序編譯所需的時間 計算機執(zhí)行每條指令所需的時間計算機執(zhí)行每條指令所需的

13、時間 程序中指令反復執(zhí)行的次數(shù)程序中指令反復執(zhí)行的次數(shù)*定義定義 語句頻度：語句反復執(zhí)行的次數(shù)語句頻度：語句反復執(zhí)行的次數(shù)n程序運轉(zhuǎn)時間算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 7國家示范性軟件學院 http:/ 2006 秋漸近時間復雜度時間復雜度漸近時間復雜度時間復雜度Tn 算法中根本操作反復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)fn，算法的時間度量記作： Tn= O fn 它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和fn的增長率一樣。漸近空間復雜度空間復雜度漸近空間復雜度空間復雜度Sn Sn= O gn運算法那么：運算法那么： 設：設：T1(n)=O( f(n) )，T2(n)=O( g(n

14、) ) 加法規(guī)那么：加法規(guī)那么：T1(n)+T2(n) = O( max f(n), g(n) ) 乘法規(guī)那么：乘法規(guī)那么：T1(n) T2(n) = O( f(n) g(n) )算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 8國家示范性軟件學院 http:/ 2006 秋程序運轉(zhuǎn)時間比較程序運轉(zhuǎn)時間比較 Tn=OfnT(n)n01000200030005101520252nn3100n5n2logn2100n T(n)算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 9國家示范性軟件學院 http:/ 2006 秋設：T(x) ： 取變量或常量x之值所耗費時間T(.V)： 取變量V之地址所耗費的時間T(=)

15、 ： 賦值所耗費時間T() ： 執(zhí)行根本運算所耗時間T(call/return)：執(zhí)行函數(shù)調(diào)用和前往所耗時間T(par) ： 將參數(shù)par傳給函數(shù)所耗費時間算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 10國家示范性軟件學院 http:/ 2006 秋(1) 表達式和賦值語句表達式和賦值語句 exp:=常數(shù)常數(shù) | 變量變量 | F-name(e1,e2,em) | (exp exp) T(v=exp)=T(.v)+T(=)+T(exp) T(exp exp)=T(exp)+T()+T(exp) T(F-name(e1,e2,em)=T(call/return)+mT(par)+T(F-body)

16、例：例： T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b) 相應的匯編程序為：相應的匯編程序為： load a in R1 load b in R2 add R2 to R1 load .c in R2 store R1 in R2通常取O(1)算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 11國家示范性軟件學院 http:/ 2006 秋(2) 語句序列語句序列 T(s1,s2,sk)=maxT(s1),T(s2),T(sk)(3) 條件語句條件語句 T( if (B) s1 else s2)=T(B)+T(else)+maxT(s1),T(s2) 通常取通常取T(B)+T(e

17、lse)=O(1) T(if(B) s )=O(1)+T(s)(4) Switch語句語句 設語句設語句s switch(E) case E1: S1; case Ek: Sk; default : Sm T(s)=T(E)+T(Ei)+maxT(s1),T(sk),T(sm) O(1) ki=1算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 12國家示范性軟件學院 http:/ 2006 秋(5) for語句語句 T( for(i=1;i=n;i+) s ) =(T(s)+T(i=1)+T(i=n)+T(i+)+T(for)O(1)(6) while語句語句 while(B) s i=0;while

18、(B) s ; i+ 設設RT0表示某一次循環(huán)開場執(zhí)行時的絕對時間表示某一次循環(huán)開場執(zhí)行時的絕對時間 關于循環(huán)的定時不變式關于循環(huán)的定時不變式RT為為 RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j) 其中：其中：T(while)代表測試循環(huán)終止條件所耗時間代表測試循環(huán)終止條件所耗時間 T(j)代表跳回循環(huán)頭所耗時間代表跳回循環(huán)頭所耗時間 可簡化成：可簡化成：T(j)=T(while) T(while(B)s)=RT-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while)算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 13國家示范性軟件學院 http:/ 20

19、06 秋(7) 函數(shù)調(diào)用函數(shù)調(diào)用 遞歸調(diào)用：遞歸調(diào)用：被調(diào)用子函數(shù)運轉(zhuǎn)時間被調(diào)用子函數(shù)運轉(zhuǎn)時間 非遞歸調(diào)用：求解遞歸方程非遞歸調(diào)用：求解遞歸方程(8) goto語句語句 goto語句破壞了程序構(gòu)造語句破壞了程序構(gòu)造 普通對普通對goto語句限制運用語句限制運用 對有條件的對有條件的goto轉(zhuǎn)移可忽略不計轉(zhuǎn)移可忽略不計算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 14國家示范性軟件學院 http:/ 2006 秋Void BUBBLE(A)int An; int I,j,temp; for(i=0;i=i+1;j-) O(n-i-1) if(Aj-1Aj) O(n-i-1) 1) O(n(n-1)/2

20、) temp=Aj-1; O(1) O(1) =(n-i-1) =O(n2) Aj-1=Aj; O(1) O(1) Aj=temp; O(1) n-2i=0算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 15國家示范性軟件學院 http:/ 2006 秋舉例：舉例： s = 0 ; f(n) = 1; T1(n) = O(f(n) = O(1) 常量階常量階 for ( i=1 ; i = n ; +i ) +x; s += x; f(n) = 3n+1; T2(n) = O(f(n) = O(n) 線性階線性階 for ( i=1; i=n ; +i ) for( j=1 ; j =n ; +j )

21、 +x ; s += x; f(n) = 3n2+2n+1; T3(n) = O(f(n) = O(n2) 平方階平方階 for ( i=1; i=n ; +i ) for ( j=1 ; j =n ; +j ) cij = 0; for ( k=1 ; k 1 f( n ) = G1+f( n 1) f( n 1) = G2 + f( n 2) f( n 2) = G3 + f( n 3) f( 2 ) = Gn-1 + f( 1 )+ f( 1 ) = C f( n ) = G1 + G2 + G3 + Gn-1 + C f( n ) = n G T( n ) = O( f( n ) )

22、= O( n )算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 17國家示范性軟件學院 http:/ 2006 秋int sort(i,j)int i,j; if(i=j) return(xi); else m=(i+j-1)/2; return(merge(sort(i,m),sort(m+1),j); 這是一個快速排序算法merge的運轉(zhuǎn)時間正比于nn是2的冪設T(n)是sort最差情況下的運轉(zhuǎn)時間，那么T(n) (c1+c2)nlogn+c1 c1 n=12T(n/2)+c2n n1n一類遞歸方程的求解算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 18國家示范性軟件學院 http:/ 2006 秋猜解

23、法：猜解法： 首先猜出一個解首先猜出一個解f(n)的方式，令其帶有待定參數(shù)；在歸納的方式，令其帶有待定參數(shù)；在歸納推理過程中確定待定參數(shù)，并利用方程證明推理過程中確定待定參數(shù)，并利用方程證明T(n) f(n)。 假設推理過程可以完成且待定參數(shù)可以確定，那么求解終了。假設推理過程可以完成且待定參數(shù)可以確定，那么求解終了。 f(n)可以是可以是 O(1) , O(n) , O(nlogn) , O(n2)等等。等等。設有：設有： T(n) c1 n=12T(n/2)+c2n n1猜測猜測1：對參數(shù)：對參數(shù)a，T(n) anlogn，帶入，帶入n=1，由于，由于anlogn=0 雖然滿足雖然滿足T(

24、1) c1，但它與，但它與a無關，無法確定無關，無法確定a與與c1關系。關系。 此猜測失敗。此猜測失敗。算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 19國家示范性軟件學院 http:/ 2006 秋猜測猜測2：T(n)=anlogn+b，當，當n=1時，只需時，只需bc1即可。即可。 當當n2時，設對一切的時，設對一切的 k1 的齊次解是O(nlogc )，且對特解有如下結(jié)論：(1)假設ad(c)，那么特解是O(ak)，或O(nlogc ),即特解與齊次解同階(2)假設ad(c)，那么特解是O(d(c)k)，或O(nlogcd(c)即特解與d同階(3)假設a=d(c)，那么特解是齊次解的logcn

25、。 aa算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 24國家示范性軟件學院 http:/ 2006 秋根本思想：分而治之。將一個規(guī)模為n的問題分解為k個規(guī)模較小 的子問題，這些子問題相互獨立且與原問題一樣。遞 歸地解這些子問題，然后將各子問題的解合并得到原 問題的解。 設問題輸入數(shù)據(jù)A0.n-1，函數(shù)dac(p,q)求子問題Ap,q的解。對函數(shù)dac的初次調(diào)用是dac(0,n-1)。int dac(int p, int q) if(small(p,q) return(G(p,q); else (m1,mk)=divide(p,q); return(Combine(dac(p,m1),dac(m1+

26、1,m2), ,dac(mk+1,q); 分治方法與軟件設計的模塊化方法非常類似。為理處理一個大的問題，可以： 1) 把它分成兩個或多個更小的問題； 2) 分別處理每個小問題； 3) 把各小問題的解組合起來，即可得到原問題的解答。小問題通常與原問題類似，可以遞歸運用分治戰(zhàn)略來處理。 n分治分治Divide and Conquer Divide and Conquer 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 25國家示范性軟件學院 http:/ 2006 秋1、整數(shù)乘法、整數(shù)乘法 求兩個n位數(shù)之積，傳統(tǒng)方法需求O(n2)次比較運算，運用分治法可以將運算次數(shù)的階降到O(nlog3) O(n1.59

27、)。 設x和y都是n位數(shù)，n是2的冪，將x和y各分成兩半，每一半都是n/2位數(shù)，那么xy的積可寫成： xy=(a2n/2+b) (c2n/2+d) =ac2n+(ad+bc) 2n/2+bd也可寫成： xy=ac2n+ac+ (a-b) (d-c) +bd) 2n/2+bdabcdx=y=算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 26國家示范性軟件學院 http:/ 2006 秋int mult(int x, int y,int n) if(n1算法分析： T(n)=O(nlog3)解： T(n)=3knlog3-2kn算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 27國家示范性軟件學院 http:/

28、 2006 秋例：設 x=3141, y=5327, 利用分治法求xy31415327x=y=x=3141 a=31 b=41 a-b=-10y=5327 c=53 d=27 d-c=-26 ac=(1643)*, bd=(1107)*, (a-b) (d-c)=(260)*xy=ac104+(ac+(a-b) (d-c)+bd) 102+bd =(1643)*104+(1643)*+(260)*+(1107)* 102+(1107)* =(16732107)*a=31 a1=3 b1=1 a1-b1=2c=53 c1=5 d1=3 d1-c1=-2 a1c1=15, b1d1=3, (a1-

29、b1) (d1-c1)=-4ac=15102+(15+3-4)101+3=1632b=41 a2=4 b2=1 a2-b2=3d=27 c2=2 d2=7 d2-c2=5 a2c2=8, b2d2=7, (a2-b2) (d2-c2)=15bd=8102+(8+7+15)101+7=1107a-b=10 a3=1 b3=0 a3-b3=1d-c=26 c3=2 d3=6 d3-c3=4 a3c3=2, b3d3=0, (a3-b3) (d3-c3)=4(a-b) (d-c)=2102+(2+0+4) 101+0=260算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 28國家示范性軟件學院 http:/

30、 2006 秋2、求兩個矩陣的積、求兩個矩陣的積A11 A12A21 A22B11 B12B21 B22C11 C12C21 C22 C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22將A和B分別等分成4個小矩陣,每個元素就是一個(n/2) x(n/2)矩陣假設用(n/2) (n/2)矩陣的m次相乘和a次相加減可以算出Cij，那么遞歸運用這種算法，對nn矩陣之積的時間開銷滿足： T(n)2其中第一項為哪一項計算m對(n/2) (n/2)矩陣之積的時間開銷,(n/2)2個數(shù)第二項是a次矩陣相加的時間開銷。上是可

31、變換成： 4/aT(n)=4m/aT(n/2)+n2 U(n)=4m/aU(n/2)+n2其中d(n)=n2是倍積函數(shù)，只需ma就有4m/ad(c)，T(n)=O(nlogm)m=8,a=4，T(n)=O(n3)算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 29國家示范性軟件學院 http:/ 2006 秋V.Strassen矩陣矩陣引理引理2.1 兩個兩個22矩陣矩陣(元素來自恣意的環(huán)元素來自恣意的環(huán))之積可以用之積可以用7次相乘和次相乘和18次相加次相加(減減)完成。完成。M1=(A11A12)(B21+B22) M2=(A11+A22)(B11+B22)M3=(A11A21)(b11+B12)

32、M4=(A11+A12)B22M5=A11(B12-B22)M6=A22(B21B11)M7=(A21+A22)B11C11=M1+M2-M4+M6C12=M4+M5C21=M6+M7C22=M2M3+M5M7定理定理2.2 兩個兩個nn的矩陣的矩陣(元素來自恣意的環(huán)元素來自恣意的環(huán))之積可用之積可用O(nlog7)次次 運算完成運算完成 證：設證：設n=2k，T(n)是計算兩個是計算兩個nn矩陣之積，由引理矩陣之積，由引理2.1得得 T(n)=7T(n/2)+18(n/2)2，n=2 故有：故有：T(n)=O(nlog7)算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 30國家示范性軟件學院 htt

33、p:/ 2006 秋在對問題進展分割時，應使各子問題的數(shù)據(jù)量堅持相等或盡能夠相等。堅持平衡是算法設計的一條根本原那么。例如：常見的是“冒泡分類算法就是一個不平衡的例子。 在分治時將輸入數(shù)據(jù)a1,a2,an分成很不平衡的數(shù)據(jù)段： 從左至右掃描a1,a2,an并求出minai,1=i1 T(n)=n(n-1)/2=O(n2)思索平衡：無妨設n是2的冪。將a1,a2,an分成兩個子序列：a1,a2,an/2和a(n/2)+1,an。先對每個子序列進展分類，然后對已分類的子序列進展歸并最多需求n-1次比較，合并成一個有序序列。T(n) =0 n=12T(n/2)+n-1 n1 T(n)=O(nlogn

34、)n平衡平衡算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 31國家示范性軟件學院 http:/ 2006 秋 運用部分最正確戰(zhàn)略以求到達全局最正確結(jié)果。運用部分最正確戰(zhàn)略以求到達全局最正確結(jié)果。 給定輸入數(shù)據(jù)為給定輸入數(shù)據(jù)為A1,A2,An，對解附有某些約束條件，對解附有某些約束條件和表示最正確結(jié)果的目的函數(shù)，欲求滿足約束條件的子集和表示最正確結(jié)果的目的函數(shù)，欲求滿足約束條件的子集Aik,使使目的函數(shù)值到達最大或最小。目的函數(shù)值到達最大或最小。 滿足約束條件的恣意子集叫做可用解，使給定的目的值到達滿足約束條件的恣意子集叫做可用解，使給定的目的值到達最大或最小的可用解叫做最正確解。最終目的是求全局最正

35、確解。最大或最小的可用解叫做最正確解。最終目的是求全局最正確解。Dataset Gready(A, n)LIST A ; int n ; solution = ； for( i = 1; i = n; i+ ) x = select(A); if ( feasible( solution, x ) ) solution = union ( solution , x ) ; return solution ; select 對 A 確定一種取值方法；每步對一個x=Ai作出判別：x能否可以包含在最正確解中？假設x參與部分最正確解時就產(chǎn)生不可用解，放棄x，另作選擇。union將x和solution結(jié)

36、合成新的解向量,并修正目的函數(shù)的值。n貪婪法貪婪法算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 32國家示范性軟件學院 http:/ 2006 秋在貪婪算法greedy method中采用逐漸構(gòu)造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策在一定的規(guī)范下。決策一旦作出，就不可再更改。作出貪婪決策的根據(jù)稱為貪婪準那么greedy criterion。 例找零錢例找零錢 一個小孩買了價值少于一個小孩買了價值少于1美圓的糖，并將美圓的糖，并將1美圓的錢交給售貨員。美圓的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設提供了數(shù)目不限的面值為售貨員希望用數(shù)目最少的硬幣找給小孩。假設提供了數(shù)目不限

37、的面值為2 5美分、美分、1 0美分、美分、5美分、及美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次參與一個硬幣。選擇硬幣時所采用的貪婪準那么如下：每一次選擇應使每次參與一個硬幣。選擇硬幣時所采用的貪婪準那么如下：每一次選擇應使零錢數(shù)盡量增大。為保證解法的可行性即：所給的零錢等于要找的零錢零錢數(shù)盡量增大。為保證解法的可行性即：所給的零錢等于要找的零錢數(shù)，所選擇的硬幣不應使零錢總數(shù)超越最終所需的數(shù)目。數(shù)，所選擇的硬幣不應使零錢總數(shù)超越最終所需的數(shù)目。 假設需求找給小孩假設需求找給小孩6 7美分，首先入選的是兩枚美分，首先入選的是兩枚2 5美分的

38、硬幣，第三美分的硬幣，第三枚入選的不能是枚入選的不能是2 5美分的硬幣，否那么硬幣的選擇將不可行零錢總數(shù)超美分的硬幣，否那么硬幣的選擇將不可行零錢總數(shù)超越越6 7美分，第三枚應選擇美分，第三枚應選擇1 0美分的硬幣，然后是美分的硬幣，然后是5美分的，最后參與兩個美分的，最后參與兩個1美分的硬幣。美分的硬幣。背包問題背包問題設有設有n個對象和一個背包。對象的分量為個對象和一個背包。對象的分量為wi。背包容量為。背包容量為M(分量分量)。假設將對象假設將對象i的一部分的一部分xi(0 xi1;xi表示重物表示重物wi的幾分之幾的幾分之幾)放入背包，放入背包，那么得增益那么得增益pixi，其中，其中

39、pi叫做重物叫做重物wi的增益率。目的的增益率。目的:在在n個對象中選個對象中選取假設干對象，將背包裝滿取假設干對象，將背包裝滿(所選對象的總分量不超越所選對象的總分量不超越M),使總增使總增益最大。益最大。max(pixi) 1in約束條件：wixiM 0 xi1, pi0, wi0, 1in 滿足的恣意集合x1,x2,xn就是可用解使最大的可用解即最正確解1in算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 34國家示范性軟件學院 http:/ 2006 秋三種貪婪戰(zhàn)略：(1)部分最大增一戰(zhàn)略：即在第i步選過之后第i+1步將當前增益 最大的未選對象裝入背包；假設該對象太大而溢出背包，那么裝 入該對

40、象的幾分之幾。(2)貪婪戰(zhàn)略之二：背包容量部分耗費最小戰(zhàn)略。即按先輕后重 的順序來選擇對象。(3)貪婪戰(zhàn)略之三：耗費單位容量，獲取部分最大增益戰(zhàn)略。即 按pi/wi非添加的順序來選擇對象。算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 35國家示范性軟件學院 http:/ 2006 秋x1,x2,x3wixipixi1(1/2,1/3,1/4)16.524.252(1,2/15,0)2028.23(0,2/3,1)20314(0,1,1/2)2031.5例：設n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)按戰(zhàn)略1，對象1的增益率p1最大，取x1

41、=1,那么背包容量尚余M-w1=2;對象2的增益率次之,但w2=15,不能全部裝入,故令x2=2/15,得解2。按戰(zhàn)略2，首先取x3=1,次取x2=2/3,得解3。按戰(zhàn)略3，得解4，這才是最正確解。Void KnapSack (LIST w ; int m ; LIST &x ; int n ) int i , cu ; for ( i = 1 ; i = n ; i+ ) xi = 0 ; cu = M ; for ( i = 1 ; i cu ) goto L; xi = 1 ; cu = cu wi ; L : if ( i = n ) xi = cu / wi ;Pi/wi=(

42、1.4,1.6,1.5)算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 36國家示范性軟件學院 http:/ 2006 秋定理定理2.3 假設假設 p1/w1p2/w2pn/wn 那么算法那么算法Knapsack對給定的對給定的 背包問題生成全局最正確解。背包問題生成全局最正確解。 證明見教材證明見教材P42略。略。算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 37國家示范性軟件學院 http:/ 2006 秋 ) 1,(10 ) 1,( 10False 0False 0True),(時所選物品中包括時所選物品中不包括且或物品件數(shù)不能為負數(shù)且總重量不能為負數(shù)此時背包問題一定有解nwnnwsKNAPnwnsn

43、sKNAPnsssnsKNAP算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 38國家示范性軟件學院 http:/ 2006 秋當一個問題的解可以看成是以序列斷定的結(jié)果時，可以用動態(tài)規(guī)劃方法設計出這類問題的求解算法。來源于二十世紀五十年代貝爾曼B.E.Bellman屬于現(xiàn)代控制實際的一部分以長久利益為目的的一系列決策最優(yōu)化原理，可歸結(jié)為一個遞推公式又稱為對階段規(guī)劃，特點表達在多階段性n動態(tài)規(guī)劃動態(tài)規(guī)劃算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 39國家示范性軟件學院 http:/ 2006 秋背包問題的解可以看成是一序列斷定的結(jié)果，這里必需決議xi(1in)的取值。我們可以用不盡的方式首先做關于x1的斷定

44、,然后關于x2,x3,等等.最后產(chǎn)生一個最正確的斷定序列x1,x2,xn,使目的函數(shù)pixi的值最大。最正確原理最正確原理一個最正確斷定序列有這樣一個性質(zhì)：無論該序列是從什么初始一個最正確斷定序列有這樣一個性質(zhì)：無論該序列是從什么初始形狀開場初次判別的，其后續(xù)的判別隊初次判別所產(chǎn)生的形狀形狀開場初次判別的，其后續(xù)的判別隊初次判別所產(chǎn)生的形狀而言，必構(gòu)成最正確斷定序列。而言，必構(gòu)成最正確斷定序列。貪婪法與動態(tài)規(guī)劃方法之間的本質(zhì)區(qū)別：貪婪法與動態(tài)規(guī)劃方法之間的本質(zhì)區(qū)別：貪婪法只生成一個斷定序列，而動態(tài)規(guī)劃方法那么能夠產(chǎn)生許多貪婪法只生成一個斷定序列，而動態(tài)規(guī)劃方法那么能夠產(chǎn)生許多斷定序列。斷定序列

45、。算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 - 40國家示范性軟件學院 http:/ 2006 秋maxpixi1ij例：例：0/1背包問題用背包問題用Knap(1,I,y)表示下述表示下述0/1背包問題背包問題約束條件：約束條件：wixiy， xi=0 或或 1 1ij1ij那么0/1背包問題是knap(1,n,M)wiziM-w1 ，pizipixi 2in2in2in設：設：y1,y2,yn是是x1,x2,xn所取所取0/1值的最正確序列。值的最正確序列。l 假設y1=0, y2,y3,yn必構(gòu)成關于Knap(2,n,M)的最正確序列。不然，y1,y2,yn就不是Knap(1,n,M)的最正確序列。l 假設y1=1,那么y2,y3,yn必是關于knap(2,n,M-w1)的最正確序列,如不