文本算法1概述

1、算法設(shè)計與分析晶kjhe，計算機算法設(shè)計與分析（第4版）， 電子工業(yè)ß課程方式：占總成績的60%。期末閉卷ß成績（作業(yè)、小和課堂考勤等）、ß實驗：占總成績的40%。第1章算法概述學習要點:· 理解算法的概念。· 理解什么是程序，程序與算法的區(qū)別和內(nèi)在。· 掌握算法的計算復(fù)雜性概念。· 掌握算法漸近復(fù)雜性的數(shù)學表述。· 掌握用C+語言描述算法的方法。算法(Algorithm)ß算法是指解決問題的法或一個過程。ß算法是若干指令的有窮序列，滿足性質(zhì)：ß(1)輸入：有外部提供的量作為算法的輸入

2、。ß(2)輸出：算法產(chǎn)生至少一個量作為輸出。ß(3)確定性：組成算法的每條指令是清晰，無歧義的。ß(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時間也是有限的。程序(Program)ß程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。ß程序可以不滿足算法的性質(zhì)(4)。ß例如操作系統(tǒng)，是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。ß操作系統(tǒng)的各種任務(wù)可看成是單獨的問題，每一個問題由操作系統(tǒng)中的一個子程序通過特定的算法來實現(xiàn)。該子程序得到輸出結(jié)果后便終止。問題求解(Problem Solving)理解問題精確解或近似解選

3、擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計策略設(shè)計算法證明正確性分析算法設(shè)計程序算法復(fù)雜性分析ß算法復(fù)雜性 = 算法所需要的計算機ß算法的時間復(fù)雜性T(n)；ß算法的空間復(fù)雜性S(n)。ß其中n是問題的規(guī)模（輸入大?。?。算法的時間復(fù)雜性ß（1）最壞情況下的時間復(fù)雜性Tmax(n) = max T(I) | size(I)=n ßß（2）最好情況下的時間復(fù)雜性Tmin(n) = min T(I) | size(I)=n ßß（3）平均情況下的時間復(fù)雜性å p(I )T (I )Tavg(n) =ßsize( I

4、 )=nß其中I是問題的規(guī)模為n的實例，p(I)是實 例I出現(xiàn)的概率。算法漸近復(fù)雜性ßt(n) -算法漸近復(fù)雜性ÞT(n) ®¥ , as n®¥ ;Þ(T(n) - t(n) )/ T(n) ®0 ，as n®¥Þt(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。Þ在數(shù)學上， t(n)是T(n)的漸近表的主項。它比T(n) 簡單。，是T(n)略去低階項留下漸近分析的記號在下面的討論中，對所有n，f(n) ³ 0，g(n) ³ 0。（1） 漸近上

5、界記號O正常數(shù)c和n0使得對所有n³ n0有：0 £ f(n) £ cg(n) 。則稱f(n) = O(g(n)表示算法運行時間的上界比如：f(n)=2*n+2=O(n) 比如：f(n)=2*n+2=O(n2)（2） 漸近下界記號W正常數(shù)c和n0使得對所有n³ n0有：0£ cg(n) £ f(n) 。則稱f(n) =W (g(n)表示算法運行時間的下界比如：f(n)=2*n2+3*n+2=(n2) 比如：f(n)=2*n2+3*n+2=(n)比如：f(n)=2*n2+3*n+2=(1)ßßßß

6、ßßßßßßßßß（3）非緊上界記號oß對于任何正常數(shù)c>0，正數(shù)和n0 >0使得對所有n³n0有：0 £ f(n)<cg(n) 。則稱f(n)= o(g(n) 。ß小o記號表示復(fù)雜度的上界，但是一定不等于下界。ßf(n)=2n2+3n+5=o(n3)或者f(n)=o(n4)或者f(n)=o(n5)ß（4）非緊下界記號wß對于任何正常數(shù)c>0，正數(shù)和n0 >0使得對所有n³n0有：0 £

7、 cg(n) < f(n) 。則稱f(n) =w (g(n) 。ßw記號表示復(fù)雜度的下界，但是一定不等于上界。ß（5）緊漸近界記號QßQ (g(n) = f(n) |正常數(shù)c1,c2和n0使得對所有n³n0有：c1g(n) £ f(n) £ c2g(n) ß表示所有階數(shù)與g(n)相同的函數(shù)集合ßf(n)=2n2+3n+5= Q(n2)ß定理1： Q (g(n) = O (g(n) Ç W (g(n)漸近分析記號的若干性質(zhì)ß（1）傳遞性：ßf(n)= Q(g(n)， g(

8、n)= Q(h(n)f(n)= Q(h(n)；f(n)= O (h(n)；f(n)= W(h(n)；f(n)= o(h(n)；f(n)= w (h(n)；Þßf(n)= O(g(n)， g(n)= O (h(n) Þßf(n)= W(g(n)， g(n)= W (h(n) Þßf(n)= o(g(n)， g(n)= o(h(n)Þßf(n)= w(g(n)， g(n)= w (h(n) ÞLevel 2ß（2）反身性：ßf(n)= Q(f(n)；ßf(n)= O(f(n)；&

9、#223;f(n)= W(f(n).ß（3）對稱性：ßf(n)= Q(g(n) Û g(n)= Q (f(n) .ß（4）互對稱性：ßf(n)= O(g(n) Û g(n)= W (f(n) ；ßf(n)= o(g(n) Û g(n)= w (f(n) ；Level 2ß（5）算術(shù)運算：ß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) ；

10、23;O(cf(n) = O(f(n) ；ßg(n)= O(f(n) Þ O(f(n)+O(g(n) = O(f(n) 。Level 2算法漸近復(fù)雜性分析中常用函數(shù)ß（1）單調(diào)函數(shù)ß單調(diào)遞增：m £ n Þ f(m) £ f(n) ;ß單調(diào)遞減：m £ n Þ f(m) ³ f(n);ß嚴格單調(diào)遞增：m < n Þ f(m) < f(n);ß嚴格單調(diào)遞減：m < n Þ f(m) > f(n).ß（2）取整函數(shù)&

11、#223;ë x û ：不大于x的最大整數(shù)；ßé x ù ：不小于x的最小整數(shù)。取整函數(shù)的若干性質(zhì)ßx-1 < ë x û £ x £ é x ù < x+1；ßë n/2 û + é n/2 ù = n;ß對于n ³ 0，a,b>0，有：ßé é n/a ù /b ù = é n/ab ù ;ßë

12、ë 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ù)。Level 2ß（3）多項式函數(shù)ßp(n)= a0+a1n+a2n2+adnd； ad>0;ßp(n) = Q(nd);ßf(n) = O(nk) Û f(

13、n)多項式有界；ßf(n) = O(1) Û f(n) £ c;ßk ³ d Þ p(n) = O(nk) ;ßk £ d Þ p(n) = W(nk) ;ßk > d Þ p(n) = o(nk) ;ßk < d Þ p(n) = w(nk) .（4）指數(shù)函數(shù)對于正整數(shù)m,n和實數(shù)a>0:ßßa0=1;a1=a ;a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n ;a>

14、;1 Þ an為單調(diào)遞增函數(shù);ßßßßßßßnba>1 ÞÞ n= o(a )bn= 0limßann®¥i= 1 + x +ex2!3!i!i=0ßex ³ 1+x;ß|x| £1 Þ 1+x £ ex £ 1+x+x2 ;ßex = 1+x+ Q(x2),as x®0;x önælimç1 += ex÷n®¥

15、èn øLevel 0ß（5）對數(shù)函數(shù)ßlog n = log2n;ßlg n = log10n;ßln n = logen;ßlogkn = (log n)kl;ßlog log n = log(log n);ßfor a>0,b>0,c>0a = blogb alogc (ab) = logc a + logcban= n logb alogba = logc alogblog bclogb (1/ a) = -logba1loga =blogbaa logb c= clogb a2

16、5ß|x| £1 Þln(1 +-L.2345xßfor x > -1, 1 +logb nlogbnßfor any a > 0, Þ log n = o(n )= lim= 0balimalog nan®¥ (2)nn®¥Level 0ß（6）階乘函數(shù)n = 0n > 0n!= ì1ín(n - 1)!în!= 1× 2 × 3LnßStirlings approximationæ n 

17、6;n ææ 1 öön!=÷ ç1+ Qç÷÷2 nçè e ø èè n øøæ n ön11ea nn!=< <2 nç÷n12n + 112nè e øn!= o(nn )n!= w (2n )log(n!) = Q(n log n)Level 2算法分析中常見的復(fù)雜性函數(shù)小規(guī)模數(shù)據(jù)中等規(guī)模數(shù)據(jù)用c+描述算法Level 0（1）選擇語句：ß（1.1

18、)if 語句：ßif (expression) statement; else statement;（1.2)？語句：ßßexp1?exp2:exp3 y= x>9 ? 100:200;if (x>9) y=100;else y=200;等價于：Level 0（1.3) switch語句：switch (expression) case 1:statement sequence; break;case 2:statement sequence; break;¼default:statement sequence;Level 0（2）迭代語句：

19、ß（2.1) for 循環(huán)：ßfor (init;condition;inc) statement;ß（2.2) while 循環(huán)：ßwhile (condition) statement;ß（2.3) do-while 循環(huán)：ßdostatement;ßß while (condition);Level 0（3）跳轉(zhuǎn)語句：ß（3.1) return語句：return expression;ßß（3.2) goto語句：goto label;¼label:ß

20、3;ßLevel 0（4）函數(shù)：return-type function name(para-list)body of the functionß例：int max(int x,int y)return x>y?x:y;Level 0（5）模板template ：template <class Type> Type max(Type x,Type y)return x>y?x:y;int i=max(1,2)；double x=max(1.0,2.0)；Level 0（6）動態(tài)分配：ß（6.1）運算符new ：ß運算符new用于動

21、態(tài)分配。ßnew返回一個指向所分配空間的指針。ß例：int *x；y=new int；*y=10；ß也可將上述各語句作適當合并如下：ßint *y=new int；*y=10；ß或 int *y=new int(10)；ß或 int *y；y=new int(10)；Level 0（6.2）一維數(shù)組：ß為了在運行時創(chuàng)建一個大小可動態(tài)變化的一維浮點數(shù)組x，可先將x為一個float類型的指針。然后用new為數(shù)組動態(tài)地分配存儲空間。ß例：ßfloat *x=new floatn；ß創(chuàng)建一個大小為n的一

22、維浮點數(shù)組。運算符new分配n個浮點數(shù)所需的空間，并返回指向第一個浮點數(shù)的指針。ß然后可用x0，x1，xn-1來每個數(shù)組元素。Level 0（6.3）運算符delete ：ß當動態(tài)分配的用的空間?？臻g已不再需要時應(yīng)及時所占ß用運算符delete來ß例：由new分配的空間。ßdelete y；ßdelete x；分配給*y的空間和分配給一維數(shù)組x的空間。ß分別Level 0（6.4）動態(tài)二維數(shù)組：ß創(chuàng)建類型為Type的動態(tài)工作數(shù)組，這個數(shù)組有rows行和cols列。template <class Type>

23、;void Make2DArray(Type* &x,int rows, int cols)x=new Type*rows; for (int i=0;i<rows;i+)xi=new Typecols;Level 0ß當不再需要一個動態(tài)分配的二維數(shù)組時，可按以下步驟它所在for循環(huán)中為每一行所分配的空間。然后占用的空間。首先為行指針分配的空間。template <class Type>void Delete2DArray(Type* &x,int rows)for (int i=0;i<rows;i+) delete xi;delete x;

24、 x=0;空間后將x置為0，以防繼續(xù)已被的空間。ßLevel 0算法分析方法ß例：順序搜索算法template<class Type>int seqSearch(Type *a, int n, Type k)for(int i=0;i<n;i+)if (ai=k) return i; return -1;ß（1）Tmax(n) = max T(I) | size(I)=n =O(n)ß（2）Tmin(n) = min T(I) | size(I)=n =O(1)ß（3）在平均情況下，假設(shè)：的概率為p ( 0 £ p

25、£ 1 )；(a) 搜索ß(b) 在數(shù)組的每個位置i ( 0 £ i < n )搜索p/n。Tavg (n) =å p(I )T (I )size( I )=n的概率相同，均為ß= æ1× p + 2 × p + 3 × p +L + n × p ö + n × (1 - p)çn ÷nnnèøi + n(1 - p) = p(n + 1) + n(1 - p)n= p ån2i=1算法分析的則ß非遞歸算法：&

26、#223;（1）for / while 循環(huán)ß循環(huán)體內(nèi)計算時間*循環(huán)次數(shù)；ß（2）嵌套循環(huán)ß循環(huán)體內(nèi)計算時間*所有循環(huán)次數(shù)；ß（3）順序語句ß各語句計算時間相加；ß（4）if-else語句ßif語句計算時間和else語句計算時間的較大者。template<class Type>void insertion_sort(Type *a, int n)Type key;for (int i = 1; i < n; i+) key=ai;int j=i-1;while( j>=0 && aj&

27、gt;key ) aj+1=aj;j-;aj+1=key;/cost c1 c2 c3 c4 c5c6times nn-1nn-11åtin-1å(t -1)i=1in-1i=1å(ti -1)i=1/c7n-1n-n-n-1(tii=T (n) = c n + c (n -1) + c (n -1) + cti + c(ti -1) + c-1) + c7 (n -1)i=i=ß在最好情況下，ti=1, for 1 £ i <n;Tmin (n) = c1n + c2 (n -1) + c3 (n -1) + c4 (n -1) + c7