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

1、算法分析與設(shè)計(jì),算法分析與設(shè)計(jì),CS dept. 李文正樓北203 Tel: 83790366 juntao,算法分析與設(shè)計(jì),參考書目,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)代計(jì)算機(jī)常用數(shù)據(jù)結(jié)構(gòu)和算法（南大出版社），即Cormen等3人書第一版的翻譯,算法分析與設(shè)計(jì)

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

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

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

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

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

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

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使得對(duì)所有n n0有：0 f(n)0，存在正數(shù)n0 0使得對(duì)所有n n0有：0 cg(n) 0; p(n) = (nd); f(n) = O(nk) f(n)多項(xiàng)式有界； 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è)計(jì),ex 1+x; |x| 1 1+x ex 1+x+x2 ; ex = 1+x+ (x2), as x0;,算法分析與設(shè)計(jì),對(duì)數(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è)計(jì),|x| 1 for x -1, fo

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

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

12、label; label:,算法分析與設(shè)計(jì),函數(shù)： 例：,return-type function name(para-list) body of the function ,int max(int x,int y) return xy?x:y; ,算法分析與設(shè)計(jì),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è)計(jì),動(dòng)態(tài)存儲(chǔ)分配 運(yùn)算符new 運(yùn)算符new用于動(dòng)態(tài)存儲(chǔ)分配。 new返回一個(gè)指向所分配空間的指針。 例：int y；y=ne

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

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

15、ray(Type* ,算法分析與設(shè)計(jì),算法分析方法,例：順序搜索算法,template int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1; ,算法分析與設(shè)計(jì),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ù)組的每個(gè)位置i ( 0 i n )搜索成功的概率相同，均為 p/n。,算法分析與設(shè)計(jì),算法分析的基本法

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