算法分析第一章

1、介紹：張公敬Mail：辦公室：博知樓 信息安全系辦公室Phone:85953165同學自我介紹：你的姓名? 你的導師？畢業(yè)學校？本科階段學習過算法分析課程？學習過數(shù)據(jù)結構？C語言？c+？ 教材及參考教材：計算機算法設計與分析（ISBN 7-121-00001-6） 王曉東 電子工業(yè)出版社 25.5元 2005.12出版參考：算法設計與分析（ISBN 7-302-10894-3 ）鄭宗漢 鄭曉明 清華大學出版社 2004.11 32元 ALGORITHM DESIGN （算法設計）英文版 Jon Kleinberg / Eva Tardos著 68元 清華大學出版社，( ISBN 7-302-1

2、2260-1)學習及考核學習方式：授課、課堂討論與演講考核方式：平常成績：20% 課堂討論20， 作業(yè)30 出勤30， 演講 20 期末考試：80% 解釋：解釋：作業(yè)： 每章結束后布置作業(yè)，每章每人1-2題。一周內(nèi)提交作業(yè)，要求獨立完成，不得抄襲。提交含電子文檔、代碼及運行程序。，缺一次平時成績分。演講演講題目：選取每章有代表性并有一定難度練習題、或算法研究方面的文章，關于算法的設計、分析、改進、實現(xiàn)等的介紹。要求：一人一題，難度適中、表達清楚、準確.時長：20分鐘考核內(nèi)容：（電子文檔）文本內(nèi)容正確、組織合理，表達清楚、準確。時間：安排自第4周17周，提前報演講題目，人數(shù)：每周按排3人。按點名

3、冊順序。作業(yè)布置及提交Z 提交時作業(yè)時文件名寫：“13研姓名（第X章）”課后用個人郵箱發(fā)送郵件給我。主題寫2013研究生（xxx）即可。第第1章章 算法概述算法概述學習要點學習要點: 理解算法的概念。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。掌握算法的計算復雜性概念。掌握算法漸近復雜性的數(shù)學表述。解遞歸方程（將在本章結束后講解）掌握用C+語言描述算法的方法。1.1算法與程序算法與程序算法+數(shù)據(jù)結構=程序 = 算法是程序的靈魂。程序設計:行為設計+結構設計行為設計:對要解決的問題，提出達到目的需要實施的一些步驟，并對這些步驟加以必要的細化，給予定義，在此基礎上用某種方式完整地描述出來，就是行為

4、設計，其結果就是算法；結構設計是針對所要解決的問題，對數(shù)據(jù)定義數(shù)據(jù)結構（包括物理物理結構和邏輯結構結構和邏輯結構）。程序：有了好的算法、合適的數(shù)據(jù)結構，再使用某種程序設計語言加以具體實現(xiàn)，即可得到程序算法是一個有窮規(guī)則（指令）的集合。它為某個特定類型問題提供了解決問題的運算序列。（非形式化定義）算法算法(Algorithm)算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入輸入：有外部提供的量作為算法的輸入。(2)輸出輸出：算法產(chǎn)生至少一個量作為輸出。(3)確定性確定性：組成算法的每條指令是清晰，無歧義的。(4)有限性有限性：有限條指令，有限時間執(zhí)行。綜上所述

5、，所謂算法是一組定義嚴謹?shù)倪\算順序規(guī)則 程序程序(Program)程序是算法用某種程序設計語言的具體實現(xiàn)。程序可以不滿足算法的性質(zhì)(4)。例如操作系統(tǒng)，是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。操作系統(tǒng)的各種任務可看成是單獨的問題，每一個問題由操作系統(tǒng)中的一個子程序通過特定的算法來實現(xiàn)。該子程序得到輸出結果后便終止。問題求解問題求解(Problem Solving)證明正確性分析算法設計程序理解問題精確解或近似解選擇數(shù)據(jù)結構算法設計策略設計算法算法復雜性分析算法復雜性分析 算法復雜性 = 算法所需要的計算機資源算法的時間復雜性T(n)；算法的空間復雜性S(n)。其中n是問題的規(guī)模（輸入大

6、?。?。算法的時間復雜性算法的時間復雜性（1）最壞情況最壞情況下的時間復雜性 Tmax(n) = max T(I) | size(I)=n （2）最好情況最好情況下的時間復雜性 Tmin(n) = min T(I) | size(I)=n （3）平均情況平均情況下的時間復雜性 Tavg(n) = 其中I是問題的規(guī)模為n的實例，p(I)是實 例I出現(xiàn)的概率。nIsizeITIp)()()(算法漸近復雜性算法漸近復雜性T(n) , as n ;(T(n) - t(n) )/ T(n) 0 ，as n;t(n)是T(n)的漸近性態(tài)，為算法的漸近復雜性。在數(shù)學上， t(n)是T(n)的漸近表達式，是T(

7、n)略去低階項留下的主項。它比T(n) 簡單。漸近分析的記號漸近分析的記號在下面的討論中，對所有n，f(n) 0，g(n) 0。（1）漸近上界記號漸近上界記號O (omicron)O(g(n) = f(n) | 存在正常數(shù)c和n0使得對所有n n0有：0 f(n) cg(n) 表示為：f(n)= O(g(n) （=） （2）漸近下界記號漸近下界記號 （omega） (g(n) = f(n) | 存在正常數(shù)c和n0使得對所有n n0有：0 cg(n) f(n) 表示為：f(n)= (g(n) （=）（3）非緊上界記號非緊上界記號o o(g(n) = f(n) | 對于任何正常數(shù)c0，存在正數(shù)n0

8、 0使得對所有n n0有：0 f(n)0，存在正數(shù)n0 0使得對所有n n0有：0 cg(n) f(n) 等價于 f(n) / g(n) ，as n。 （）f(n) (g(n) g(n) o (f(n) （5）緊漸近界記號緊漸近界記號 (g(n) = f(n) | 存在正常數(shù)c1,c2和n0使得對所有n n0有：c1g(n) f(n) c2g(n) （ =） 定理定理1： (g(n) = O (g(n) (g(n) 漸近分析記號在等式和不等式中的意義漸近分析記號在等式和不等式中的意義f(n)= (g(n)的確切意義是：f(n) (g(n)。一般情況下，等式和不等式中的漸近記號(g(n)表示(g

9、(n)中的某個函數(shù)。例如：2n2 + 3n + 1 = 2n2 + (n) 表示 2n2 +3n +1=2n2 + f(n)，其中f(n) 是(n)中某個函數(shù)。等式和不等式中漸近記號O,o, 和的意義是類似的。漸近分析中函數(shù)比較漸近分析中函數(shù)比較f(n)= O(g(n) a b;f(n)= (g(n) a b;f(n)= (g(n) a = b;f(n)= o(g(n) a b.（2）反身性：）反身性：f(n)= (f(n)；f(n)= O(f(n)；f(n)= (f(n).（3）對稱性：）對稱性：f(n)= (g(n) g(n)= (f(n) .（4）互對稱性：）互對稱性：f(n)= O(g

10、(n) g(n)= (f(n) ；f(n)= o(g(n) g(n)= (f(n) ；（5）算術運算：）算術運算：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) 。漸近分析記號的若干性質(zhì)漸近分析記號的若干性質(zhì)（1）傳遞性：）傳遞性：f(n)= (g(n)， g(n)= (h(n) f(n)= (h(n)；f(n)= O(g(n)， g(n)= O (h(n)

11、 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)；規(guī)則O(f(n)+O(g(n) = O(maxf(n),g(n) 的證明：證明：對于任意f1(n) =O(f(n) ，存在正常數(shù)c1和自然數(shù)n1，使得對所有n n1，有f1(n) c1f(n) 。類似地，對于任意g1(n) = O(g(n) ，存在正常數(shù)c2和自然數(shù)n2，使得對所有n n2，有g1(n) c2g(n) 。令c3=maxc1,

12、 c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。則對所有的 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) .算法漸近復雜性分析中常用函數(shù)算法漸近復雜性分析中常用函數(shù)（1）單調(diào)函數(shù)）單調(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 f(n).（2）取整函數(shù)）取整函數(shù) x ：不大于x的最大整數(shù)； x

13、：不小于x的最小整數(shù)。 取整函數(shù)的若干性質(zhì)取整函數(shù)的若干性質(zhì) x-1 x x x 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ù)。（3）多項式函數(shù)）多項式函數(shù) p(n)= a0+a1n+a2n2+adnd； ad0; 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) ;k 0: a0=1;

14、 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)0limnbnanex 1+x;|x| 1 1+x ex 1+x+x2 ; ex = 1+x+ (x2), as x0;032! 3!21iixixxxxexnnenx1lim（5）對數(shù)函數(shù)）對數(shù)函數(shù) log n = log2n; lg n = log10n; ln n = logen; logkn = (log n)k; log log n = log(log n); for a0,b0,c0abbalogbaabc

15、ccloglog)(loganabnbloglogbaaccblogloglogaabblog)/1 (logbaablog1logacbbcaloglog（6）階乘函數(shù)）階乘函數(shù)Stirlings approximation 00)!1(1!nnnnnnn321!nennnn112!neennnn2!nnn1211121)(!nnon )2(!nn)log() !log(nnn算法分析中常見的復雜性函數(shù)算法分析中常見的復雜性函數(shù)小規(guī)模數(shù)據(jù)小規(guī)模數(shù)據(jù)中等規(guī)模數(shù)據(jù)中等規(guī)模數(shù)據(jù)用用c+描述算法描述算法（1）選擇語句：）選擇語句：（1.1) if 語句：語句：（1.2) ？語句：？語句： if (e

16、xpression) statement;else statement; exp1?exp2:exp3 y= x9 ? 100:200; 等價于： if (x9) y=100; else y=200;（1.3) switch語句：語句：switch (expression) case 1: statement sequence; break; case 2: statement sequence; break; default: statement sequence; （2）迭代語句：）迭代語句：（2.1) for 循環(huán)：循環(huán)： for (init;condition;inc) stateme

17、nt;（2.2) while 循環(huán)：循環(huán)： while (condition) statement;（2.3) do-while 循環(huán)：循環(huán)： do statement; while (condition); （3）跳轉(zhuǎn)語句：）跳轉(zhuǎn)語句：（3.1) return語句：語句： return expression;（3.2) goto語句：語句： goto label; label:（4）函數(shù)：）函數(shù)：例：例： return-type function name(para-list) body of the function int max(int x,int y) return xy?x:y;

18、（5）模板）模板template ：template Type max(Type x,Type y) return xy?x:y; int i=max(1,2)；double x=max(1.0,2.0)；（6）動態(tài)存儲分配：）動態(tài)存儲分配：（6.1）運算符）運算符new ：運算符new用于動態(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)；（6.2）一維數(shù)組）一維數(shù)組 ：為了在運行時創(chuàng)建一個大小

19、可動態(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ù)組元素。（6.3）運算符）運算符delete ：當動態(tài)分配的存儲空間已不再需要時應及時釋放所占用的空間。用運算符delete來釋放由new分配的空間。例：例：delete y；delete x；分別釋放分配給y的空間和分配給一維數(shù)組x的空間。（6.4）動態(tài)二維數(shù)組）動態(tài)二維數(shù)組 ：創(chuàng)建類型為Type的動態(tài)工

20、作數(shù)組，這個數(shù)組有rows行和cols列。template void Make2DArray(Type* &x,int rows, int cols) x=new Type*rows; for (int i=0;irows;i+) xi=new Typecols;當不再需要一個動態(tài)分配的二維數(shù)組時，可按以下步驟釋放它所占用的空間。首先釋放在for循環(huán)中為每一行所分配的空間。然后釋放為行指針分配的空間。釋放空間后將x置為0，以防繼續(xù)訪問已被釋放的空間。template void Delete2DArray(Type* &x,int rows) for (int i=0;irows;i+) del

21、ete xi; delete x; x=0;算法分析方法算法分析方法例：順序搜索算法例：順序搜索算法templateint seqSearch(Type *a, int n, Type k) for(int i=0;in;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）在平均情況下，假設： (a) 搜索成功的概率為p ( 0 p 1 )； (b) 在數(shù)組的每個位置i ( 0 i n )搜索成功的概率相同，均為 p/

22、n。nIsizeavgITIpnT)()()()(pnnpnnpnpnp1321)1 (2)1(11pnnppninpni算法分析的基本法則算法分析的基本法則非遞歸算法：非遞歸算法：（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語句計算時間的較大者。templatevoid insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 & ajkey ) / c4 sum of ti aj+1=aj; / c5 sum of (ti-1) j-; / c6 sum of (ti-1) aj+1=key; / c7 n-1 在最好情況下，ti=1, for 1 i n;在最壞情況下，ti = i+1, for 1 i n;) 1() 1() 1() 1() 1()(7116