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

1、算法分析與設(shè)計,算法分析與設(shè)計,CS dept. 李文正樓北203 Tel: 83790366 juntao,算法分析與設(shè)計,參考書目,Aho, Hopcroft, Ullman. The Design and Analysis of Computer Algorithms. （1974版影印版，鐵道出版社） Aho, Hopcroft, Ullman. 數(shù)據(jù)結(jié)構(gòu)與算法（1983年影印本，清華出版社） Thomas H. Cormen 等4人. 算法導(dǎo)論（MIT第2版）, 高教出版社影印本 潘金貴. 現(xiàn)代計算機常用數(shù)據(jù)結(jié)構(gòu)和算法（南大出版社），即Cormen等3人書第一版的翻譯,算法分析與設(shè)計

2、,參考書目,M. H. Alsuwaiyel. Algorithms: Design Techniques and Analysis（電子工業(yè)出版社影印本，方世昌等譯） 王曉東. 算法設(shè)計與分析.（電子工業(yè)出版社） Sara Baase等. 計算機算法：設(shè)計與分析導(dǎo)論（第3版），高教出版社影印本。,算法分析與設(shè)計,第一章 預(yù)備知識,學(xué)習(xí)要點: 理解算法的概念。 理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。 掌握算法的計算復(fù)雜性概念。 掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。 掌握用C+語言描述算法的方法。,算法分析與設(shè)計,什么是算法？,算法(algorithm) 一個（由人或機器進行）關(guān)于某種運算規(guī)則的

3、集合 特點： 執(zhí)行時，不能包含任何主觀的決定； 不能有類似直覺/創(chuàng)造力等因素。,輸出,輸入,確定性 有限性,清晰、無歧義 指令執(zhí)行次數(shù)、時間,算法分析與設(shè)計,例子：,人們?nèi)粘Ｉ钪凶霾说倪^程，可否用算法描述？,如：“咸了”、“放點鹽”、“再煮一會”。 可否用計算機完成？,算法必須規(guī)定明確的量與時間； 不能含糊字眼。,算法分析與設(shè)計,當(dāng)然不是所有算法都要明確的選擇，有些概率算法進行選擇。 “隨機”“隨意” 有些問題沒有實用算法（求解精確解，需要幾百年）。,去尋找規(guī)則集,在可接受的時間內(nèi)可以算出足夠好的近似解,近似算法,啟發(fā)式算法,可以預(yù)測誤差， 且誤差足夠小,誤差無法控制， 但可預(yù)計誤差大小,算

4、法分析與設(shè)計,如何描述算法,通常，描述算法用類Pascal的結(jié)構(gòu)化編程語言。,算法分析與設(shè)計,算法的證明技巧,反證法(proof by contradication)/間接證明(indirect proof)：為了證明命題的正確性，轉(zhuǎn)而證明該命題的反命題能導(dǎo)致矛盾。 例子： 歐幾里德 定理：存在無窮多個素數(shù)。 證明：假設(shè)P為有限素數(shù)集，那么顯然 。 且有限， 將P中所有元素相乘，X表示積 Y=X+1。 對Y分析：d為Y的一個最小的且大于1的約數(shù)。,算法分析與設(shè)計,歐幾里德證明,Y1，且不要求d一定不等于Y， d一定存在。 d定為素數(shù)，否則存在一個約數(shù)z，使得z可整除Y。 又 z,矛盾,=,否則

5、,算法分析與設(shè)計,歐幾里德證明,矛盾 因此，P為無限集合。 證畢 下面衍生出找素數(shù)的一個算法：,算法分析與設(shè)計,派生出算法,function Newprime(P:整數(shù)集) 變量P為一非空有限的素數(shù)集 XP中所有元素的乘積; YX+1; d1; repeat dd+1 until d整除Y; return d,通過上述證明d定為素數(shù)且,？,算法分析與設(shè)計,派生出算法,function Newprime(P:整數(shù)集) XP中所有元素的乘積; YX+1; d1; repeat dd+1 until d整除Y; return d,通過上述證明d定為素數(shù)且,function DumpEuclid(P:

6、整數(shù)集) P為非空有限素數(shù)集 XP中最大的元素; repeat XX+1 until X是素數(shù); return d,簡化,算法分析與設(shè)計,算法的證明技巧,歸納法(induction)： 特殊=一般法則。 例子：鋪磚定理 鋪磚問題總是有解的。,mm個方格(m為2的冪),方格位置隨意,瓷磚材料形狀為,算法分析與設(shè)計,歸納法證明舉例-鋪磚定理,證明：不妨假設(shè) 。 1)當(dāng)n=0時，顯然成立；n=1時，也顯然成立； 2) ， ，對 大小的地板顯然成立，現(xiàn)四分地板得到4個相同大小的地板。,特殊方格地板,也變成存在特殊 方格地板地板,證畢,算法分析與設(shè)計,歸納法證明舉例-馬的顏色,例子：偽定理 所有馬都只有

7、一種顏色。 證明：任何一個馬的集合都只有一種顏色 =所有馬只有一種顏色。 設(shè)H為任何一個馬的集合，對H中馬數(shù)量n歸納： 1)n=0， 成立；n=1，顯然成立。 2)設(shè)H中的馬為h1, h2, hn，由于任意n-1匹馬的集合有唯一的顏色，那么 對兩個集合應(yīng)用歸納假設(shè)： H具有同種顏色。？,算法分析與設(shè)計,歸納法證明舉例-馬的顏色,， 正確 必須 ，從2=3，3=4， 不能1=2。,算法分析與設(shè)計,歸納法證明舉例-斐波納契序列,例子：Fibonacci序列 每個月一對繁殖期的兔子會產(chǎn)生一對后代，而這對后代2個月后又會繁殖。 即 第1個月買了1對兔子；第2個月仍只有1對；第3個月有2對 依此類推，如

8、兔子不死亡，那么各月的兔子數(shù)由Fibonacci序列給出：遞歸形式 序列以0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ,Fibonacci序列的算法： Function Fibonacci(n) if n0 and xi+1 to n do if Tj0使得對所有n n0有：0 f(n)0，存在正數(shù)n0 0使得對所有n n0有：0 cg(n) 0; p(n) = (nd); f(n) = O(nk) f(n)多項式有界； f(n) = O(1) f(n) c; k d p(n) = O(nk) ; k d p(n) = (nk) ; k d p(n) = o(nk) ;

9、k 0: a0=1; a1=a ; a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n ; a1 an為單調(diào)遞增函數(shù); a1 nb = o(an),算法分析與設(shè)計,ex 1+x; |x| 1 1+x ex 1+x+x2 ; ex = 1+x+ (x2), as x0;,算法分析與設(shè)計,對數(shù)函數(shù) log n = log2n; lg n = log10n; ln n = logen; logkn = (log n)kl; log log n = log(log n); for a0,b0,c0,算法分析與設(shè)計,|x| 1 for x -1, fo

10、r any a 0, , logbn = o(na),算法分析與設(shè)計,階層函數(shù) Stirlings approximation,算法分析與設(shè)計,算法分析中常見的復(fù)雜性函數(shù),算法分析與設(shè)計,小規(guī)模數(shù)據(jù),算法分析與設(shè)計,中等規(guī)模數(shù)據(jù),算法分析與設(shè)計,用c+描述算法,算法分析與設(shè)計,選擇語句： if 語句： ？語句：,if (expression) statement; else statement;,exp1?exp2:exp3 y= x9 ? 100:200; 等價于： if (x9) y=100; else y=200;,算法分析與設(shè)計,switch語句：,switch (expression

11、) case 1: statement sequence; break; case 2: statement sequence; break; default: statement sequence; ,算法分析與設(shè)計,迭代語句： for 循環(huán)： for (init;condition;inc) statement; while 循環(huán)： while (condition) statement; do-while 循環(huán)： do statement; while (condition);,算法分析與設(shè)計,跳轉(zhuǎn)語句 return語句： return expression; goto語句： goto

12、label; label:,算法分析與設(shè)計,函數(shù)： 例：,return-type function name(para-list) body of the function ,int max(int x,int y) return xy?x:y; ,算法分析與設(shè)計,template Type max(Type x,Type y) return xy?x:y; int i=max(1,2)； double x=max(1.0,2.0)；,模板template,算法分析與設(shè)計,動態(tài)存儲分配 運算符new 運算符new用于動態(tài)存儲分配。 new返回一個指向所分配空間的指針。 例：int y；y=ne

13、w int；y=10； 也可將上述各語句作適當(dāng)合并如下： int y=new int；y=10； 或 int y=new int(10)； 或 int y；y=new int(10)；,算法分析與設(shè)計,一維數(shù)組 為了在運行時創(chuàng)建一個大小可動態(tài)變化的一維浮點數(shù)組x，可先將x聲明為一個float類型的指針。然后用new為數(shù)組動態(tài)地分配存儲空間。 例： float x=new floatn； 創(chuàng)建一個大小為n的一維浮點數(shù)組。運算符new分配n個浮點數(shù)所需的空間，并返回指向第一個浮點數(shù)的指針。 然后可用x0，x1，xn-1來訪問每個數(shù)組元素。,算法分析與設(shè)計,運算符delete 當(dāng)動態(tài)分配的存儲空間已

14、不再需要時應(yīng)及時釋放所占用的空間。 用運算符delete來釋放由new分配的空間。 例：delete y；delete x； 分別釋放分配給y的空間和分配給一維數(shù)組x的空間。,算法分析與設(shè)計,動態(tài)二維數(shù)組 創(chuàng)建類型為Type的動態(tài)工作數(shù)組，這個數(shù)組有rows行和cols列。,template void Make2DArray(Type* ,算法分析與設(shè)計,當(dāng)不再需要一個動態(tài)分配的二維數(shù)組時，可按以下步驟釋放它所占用的空間。首先釋放在for循環(huán)中為每一行所分配的空間。然后釋放為行指針分配的空間。 釋放空間后將x置為0，以防繼續(xù)訪問已被釋放的空間。,template void Delete2DAr

15、ray(Type* ,算法分析與設(shè)計,算法分析方法,例：順序搜索算法,template int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1; ,算法分析與設(shè)計,Tmax(n) = max T(I) | size(I)=n =O(n) Tmin(n) = min T(I) | size(I)=n =O(1) 在平均情況下，假設(shè)： 搜索成功的概率為p ( 0 p 1 )； 在數(shù)組的每個位置i ( 0 i n )搜索成功的概率相同，均為 p/n。,算法分析與設(shè)計,算法分析的基本法

16、則,非遞歸算法： for / while 循環(huán) 循環(huán)體內(nèi)計算時間*循環(huán)次數(shù)； 嵌套循環(huán) 循環(huán)體內(nèi)計算時間*所有循環(huán)次數(shù)； 順序語句 各語句計算時間相加； if-else語句 if語句計算時間和else語句計算時間的較大者。,算法分析與設(shè)計,template void insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 / c7 n-1 ,算法分析與設(shè)計,在最好情況下，ti=1, for 1 i n; 在最壞情況下，ti i+1, for 1 i n;,算法分析與設(shè)計,對于輸入數(shù)據(jù)ai=n-i,i=0,1,n-1