計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)[王曉東][電子教案]幻燈片

1、計(jì)算機(jī)算法設(shè)計(jì)與分析（第4版）,王曉東 編著 電子工業(yè)出版社,1,第1章 算法概述,學(xué)習(xí)要點(diǎn): 理解算法的概念。 理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。 掌握算法的計(jì)算復(fù)雜性概念。 掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。 掌握用C+語(yǔ)言描述算法的方法。,2,算法(Algorithm),算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。 算法是若干指令的有窮序列，滿足性質(zhì)： (1)輸入：有外部提供的量作為算法的輸入。 (2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。 (3)確定性：組成算法的每條指令是清晰，無(wú)歧義的。 (4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。,3,程序(Progr

2、am),程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。 程序可以不滿足算法的性質(zhì)(4)。 例如操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。 操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。,4,問(wèn)題求解(Problem Solving),理解問(wèn)題,精確解或近似解 選擇數(shù)據(jù)結(jié)構(gòu) 算法設(shè)計(jì)策略,設(shè)計(jì)算法,5,算法復(fù)雜性分析,算法復(fù)雜性 = 算法所需要的計(jì)算機(jī)資源 算法的時(shí)間復(fù)雜性T(n)； 算法的空間復(fù)雜性S(n)。 其中n是問(wèn)題的規(guī)模（輸入大?。?6,算法的時(shí)間復(fù)雜性,（1）最壞情況下的時(shí)間復(fù)雜性 Tmax(n

3、) = max T(I) | size(I)=n （2）最好情況下的時(shí)間復(fù)雜性 Tmin(n) = min T(I) | size(I)=n （3）平均情況下的時(shí)間復(fù)雜性 Tavg(n) = 其中I是問(wèn)題的規(guī)模為n的實(shí)例，p(I)是實(shí) 例I出現(xiàn)的概率。,7,算法漸近復(fù)雜性,T(n) , as n ; (T(n) - t(n) )/ T(n) 0 ，as n; t(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。 在數(shù)學(xué)上， t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n) 簡(jiǎn)單。,8,漸近分析的記號(hào),在下面的討論中，對(duì)所有n，f(n) 0，g(n) 0。 （1）漸近上

4、界記號(hào)O O(g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有n n0有：0 f(n) cg(n) （2）漸近下界記號(hào) (g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有n n0有：0 cg(n) f(n) ,9,（3）非緊上界記號(hào)o o(g(n) = f(n) | 對(duì)于任何正常數(shù)c0，存在正數(shù)和n0 0使得對(duì)所有n n0有：0 f(n)0，存在正數(shù)和n0 0使得對(duì)所有n n0有：0 cg(n) f(n) 等價(jià)于 f(n) / g(n) ，as n。 f(n) (g(n) g(n) o (f(n),10,（5）緊漸近界記號(hào) (g(n) = f(n) | 存在正常數(shù)c1,c2和n

5、0使得對(duì)所有n n0有：c1g(n) f(n) c2g(n) 定理1： (g(n) = O (g(n) (g(n),11,漸近分析記號(hào)在等式和不等式中的意義,f(n)= (g(n)的確切意義是：f(n) (g(n)。 一般情況下，等式和不等式中的漸近記號(hào)(g(n)表示(g(n)中的某個(gè)函數(shù)。 例如：2n2 + 3n + 1 = 2n2 + (n) 表示 2n2 +3n +1=2n2 + f(n)，其中f(n) 是(n)中某個(gè)函數(shù)。 等式和不等式中漸近記號(hào)O,o, 和的意義是類(lèi)似的。,12,漸近分析中函數(shù)比較,f(n)= O(g(n) a b; f(n)= (g(n) a b; f(n)= (g

6、(n) a = b; f(n)= o(g(n) a b.,13,漸近分析記號(hào)的若干性質(zhì),（1）傳遞性： f(n)= (g(n)， g(n)= (h(n) f(n)= (h(n)； f(n)= O(g(n)， g(n)= O (h(n) f(n)= O (h(n)； f(n)= (g(n)， g(n)= (h(n) f(n)= (h(n)； f(n)= o(g(n)， g(n)= o(h(n) f(n)= o(h(n)； f(n)= (g(n)， g(n)= (h(n) f(n)= (h(n)；,14,（2）反身性： f(n)= (f(n)； f(n)= O(f(n)； f(n)= (f(n).

7、 （3）對(duì)稱(chēng)性： f(n)= (g(n) g(n)= (f(n) . （4）互對(duì)稱(chēng)性： f(n)= O(g(n) g(n)= (f(n) ； f(n)= o(g(n) g(n)= (f(n) ；,15,（5）算術(shù)運(yùn)算： O(f(n)+O(g(n) = O(maxf(n),g(n) ； O(f(n)+O(g(n) = O(f(n)+g(n) ； O(f(n)*O(g(n) = O(f(n)*g(n) ； O(cf(n) = O(f(n) ； g(n)= O(f(n) O(f(n)+O(g(n) = O(f(n) 。,16,規(guī)則O(f(n)+O(g(n) = O(maxf(n),g(n) 的證明：

8、 對(duì)于任意f1(n) O(f(n) ，存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有n n1，有f1(n) c1f(n) 。 類(lèi)似地，對(duì)于任意g1(n) O(g(n) ，存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有n n2，有g(shù)1(n) c2g(n) 。 令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。 則對(duì)所有的 n n3，有 f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n) = 2c3h(n) = O(maxf(n),g(n) .,17,算法漸近復(fù)雜

9、性分析中常用函數(shù),（1）單調(diào)函數(shù) 單調(diào)遞增：m n f(m) f(n) ; 單調(diào)遞減：m n f(m) f(n); 嚴(yán)格單調(diào)遞增：m f(n). （2）取整函數(shù) x ：不大于x的最大整數(shù)； x ：不小于x的最小整數(shù)。,18,取整函數(shù)的若干性質(zhì),x-1 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ù)。,19,（3）多項(xiàng)式函數(shù) p(n)= a0+a1n+a2n2+adnd； ad0; p(n) = (nd); f(n) = O(nk) f(n)多項(xiàng)式有界；

10、f(n) = O(1) f(n) c; k d p(n) = O(nk) ; k d p(n) = (nk) ; k d p(n) = o(nk) ; k d p(n) = (nk) .,20,（4）指數(shù)函數(shù) 對(duì)于正整數(shù)m,n和實(shí)數(shù)a0: 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),21,ex 1+x; |x| 1 1+x ex 1+x+x2 ; ex = 1+x+ (x2), as x0;,22,（5）對(duì)數(shù)函數(shù) log n = log2n; lg

11、n = log10n; ln n = logen; logkn = (log n)kl; log log n = log(log n); for a0,b0,c0,23,24,|x| 1 for x -1, for any a 0, , logbn = o(na),25,（6）階層函數(shù) Stirlings approximation,26,27,算法分析中常見(jiàn)的復(fù)雜性函數(shù),28,小規(guī)模數(shù)據(jù),29,中等規(guī)模數(shù)據(jù),30,用C+描述算法,31,（1）選擇語(yǔ)句： （1.1) if 語(yǔ)句： （1.2) ？語(yǔ)句：,if (expression) statement; else statement;,exp

12、1?exp2:exp3 y= x9 ? 100:200; 等價(jià)于： if (x9) y=100; else y=200;,32,（1.3) switch語(yǔ)句：,switch (expression) case 1: statement sequence; break; case 2: statement sequence; break; default: statement sequence; ,33,（2）迭代語(yǔ)句：,（2.1) for 循環(huán)： for (init;condition;inc) statement; （2.2) while 循環(huán)： while (condition) stat

13、ement; （2.3) do-while 循環(huán)： do statement; while (condition);,34,（3）跳轉(zhuǎn)語(yǔ)句：,（3.1) return語(yǔ)句： return expression; （3.2) goto語(yǔ)句： goto label; label:,35,（4）函數(shù)：,例：,return-type function name(para-list) body of the function ,int max(int x,int y) return xy?x:y; ,36,（5）模板template ：,template Type max(Type x,Type y)

14、return xy?x:y; int i=max(1,2)； double x=max(1.0,2.0)；,37,（6）動(dòng)態(tài)存儲(chǔ)分配：,（6.1）運(yùn)算符new ： 運(yùn)算符new用于動(dòng)態(tài)存儲(chǔ)分配。 new返回一個(gè)指向所分配空間的指針。 例：int x；y=new int；y=10； 也可將上述各語(yǔ)句作適當(dāng)合并如下： int y=new int；y=10； 或 int y=new int(10)； 或 int y；y=new int(10)；,38,（6.2）一維數(shù)組 ：,為了在運(yùn)行時(shí)創(chuàng)建一個(gè)大小可動(dòng)態(tài)變化的一維浮點(diǎn)數(shù)組x，可先將x聲明為一個(gè)float類(lèi)型的指針。然后用new為數(shù)組動(dòng)態(tài)地分配存儲(chǔ)空

15、間。 例： 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ù)組元素。,39,（6.3）運(yùn)算符delete ：,當(dāng)動(dòng)態(tài)分配的存儲(chǔ)空間已不再需要時(shí)應(yīng)及時(shí)釋放所占用的空間。 用運(yùn)算符delete來(lái)釋放由new分配的空間。 例： delete y； delete x； 分別釋放分配給y的空間和分配給一維數(shù)組x的空間。,40,（6.4）動(dòng)態(tài)二維數(shù)組 ：,創(chuàng)建類(lèi)型為T(mén)ype的動(dòng)態(tài)工作數(shù)組，這個(gè)數(shù)組有rows行和cols列。,template void Make2DArray

16、(Type* ,41,當(dāng)不再需要一個(gè)動(dòng)態(tài)分配的二維數(shù)組時(shí)，可按以下步驟釋放它所占用的空間。首先釋放在for循環(huán)中為每一行所分配的空間。然后釋放為行指針?lè)峙涞目臻g。 釋放空間后將x置為0，以防繼續(xù)訪問(wèn)已被釋放的空間。,template void Delete2DArray(Type* ,42,算法分析方法,例：順序搜索算法,template int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1; ,43,（1）Tmax(n) = max T(I) | size(I)=n =O(

17、n) （2）Tmin(n) = min T(I) | size(I)=n =O(1) （3）在平均情況下，假設(shè)： (a) 搜索成功的概率為p ( 0 p 1 )； (b) 在數(shù)組的每個(gè)位置i ( 0 i n )搜索成功的概率相同，均為 p/n。,44,算法分析的基本法則,非遞歸算法： （1）for / while 循環(huán) 循環(huán)體內(nèi)計(jì)算時(shí)間*循環(huán)次數(shù)； （2）嵌套循環(huán) 循環(huán)體內(nèi)計(jì)算時(shí)間*所有循環(huán)次數(shù)； （3）順序語(yǔ)句 各語(yǔ)句計(jì)算時(shí)間相加； （4）if-else語(yǔ)句 if語(yǔ)句計(jì)算時(shí)間和else語(yǔ)句計(jì)算時(shí)間的較大者。,45,template void insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 / c7 n-1 ,46,在最好情況下，ti=1, for 1 i n; 在最壞情況下，ti i+1, for 1 i n;