計(jì)算機(jī)算法設(shè)計(jì)與分析第4版

1、計(jì)算機(jī)算法設(shè)計(jì)與分析（第4版）,王曉東 編著電子工業(yè)出版社,第1章 算法概述,學(xué)習(xí)要點(diǎn): 理解算法的概念。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。了解算法在最壞情況、最好情況和平均情況下的計(jì)算復(fù)雜性概念。了解算法漸近復(fù)雜性的數(shù)學(xué)表述。,軟件（software）：程序及其各種文檔資料的總稱程序(procedure)=算法+數(shù)據(jù)結(jié)構(gòu)算法(algorithm)：解的描述（程序的靈魂）數(shù)據(jù)結(jié)構(gòu)(data structu

2、re)：現(xiàn)實(shí)世界的數(shù)據(jù)模型語(yǔ)言(language)：實(shí)現(xiàn)的工具,常見(jiàn)概念,程序：,計(jì)算機(jī)指令的序列,程序設(shè)計(jì),,行為特性設(shè)計(jì)----處理數(shù)據(jù)的步驟設(shè)計(jì),算法設(shè)計(jì),結(jié)構(gòu)性設(shè)計(jì)----對(duì)輸入輸出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì),數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì),程序=算法+數(shù)據(jù)結(jié)構(gòu),常見(jiàn)概念,通俗地講，算法是一系列解決問(wèn)題的清晰指令，也就是說(shuō)，對(duì)于符合一定規(guī)范的輸入，能夠在有限時(shí)間內(nèi)獲得所要求的輸出。,算法(Algorithm),古代謎題 一個(gè)農(nóng)夫帶著一只狼、一只

3、羊和一棵白菜來(lái)到河邊。他需要把它們用船帶到河對(duì)岸。然而，這艘船只能容下農(nóng)夫本人和另外一樣?xùn)|西（要么是狼、要么是羊，要么是白菜）。如果這個(gè)農(nóng)夫不在場(chǎng)的話，狼會(huì)吃掉羊，羊也會(huì)吃掉白菜。請(qǐng)為農(nóng)夫解決這個(gè)問(wèn)題，或證明它誤解。,算法(Algorithm),現(xiàn)代謎題 有4個(gè)人打算過(guò)橋，它們都在橋的某一端。我們有17分鐘讓他們?nèi)康竭_(dá)大橋的另一頭。時(shí)間是晚上，他們只有一只手電筒。最多只能有兩個(gè)人同時(shí)過(guò)橋，而且必須攜帶手電筒。必須步行將手電筒帶

4、來(lái)帶去，不能扔來(lái)扔去。每個(gè)人走路的速度是不同的：甲過(guò)橋需要1分鐘，乙要2分鐘，丙要5分鐘，丁要10分鐘。兩個(gè)人一起走的速度等于其中較慢的人的速度。請(qǐng)給出過(guò)橋的方案。,算法(Algorithm),算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。算法是若干指令的有窮序列，其中每一條指令表示一個(gè)或多個(gè)操作 。算法是求解一個(gè)問(wèn)題類的無(wú)二義性的有窮過(guò)程。,定義：,算法設(shè)計(jì)的任務(wù)是對(duì)各類具體問(wèn)題設(shè)計(jì)良好的算法及研究設(shè)計(jì)算法的規(guī)律和方法。常用的算法有：窮舉

5、搜索法、遞歸法、回溯法、貪心法、分治法等。,算法(Algorithm),(1)輸入：有0個(gè)或多個(gè)外部提供的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。(3)確定性：組成算法的每條指令是清晰，無(wú)歧義的。(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。(5)可行性：算法中的所有運(yùn)算都是基本的,原則上它們都能夠精確地進(jìn)行,而且進(jìn)行有窮次即可完成。,算法的性質(zhì)：,算法(Algorithm),算

6、法的形式化表示：,算法是一個(gè)四元組（Q、I、Ω、f ）,Q 是一個(gè)集合，表示計(jì)算的狀態(tài)I 是Q的一個(gè)子集，表示計(jì)算的輸入Ω 是Q的一個(gè)子集，表示計(jì)算的輸出f 是Q到它自身的一個(gè)映射，表示計(jì)算的規(guī)則,算法(Algorithm),兩個(gè)不全為0的非負(fù)整數(shù)m和n的最大公約數(shù)記為gcd(m,n).歐幾里德算法：重復(fù)應(yīng)用下列等式，直到 m mod n=0. gcd(m,n)=gcd(n,

7、m mod n),算法(Algorithm)-例子,用于計(jì)算gcd(m,n)的歐幾里德算法如果n=0，返回m的值作為結(jié)果，同時(shí)過(guò)程結(jié)束；否則，進(jìn)入下一步；m除以n，將余數(shù)賦值給r；將n的值賦給m，將r的值賦給n，返回第一步。,算法(Algorithm)-例子,計(jì)算gcd(m,n)的連續(xù)整數(shù)檢測(cè)算法將min{m,n}的值賦給t；m除以t，如果余數(shù)為0，進(jìn)入下一步，否則，進(jìn)入第四步；n除以t，如果余數(shù)為0，返回t的值作為結(jié)果，

8、否則進(jìn)入第四步；把t的值減1，返回第二步。,算法(Algorithm)-例子,中學(xué)里計(jì)算gcd(m,n)的過(guò)程找到m的所有質(zhì)因數(shù)；找到n的所有質(zhì)因數(shù)；從第一步和第二步求得的質(zhì)因數(shù)分解式中找出所有的公因數(shù)；將第三步中找到的質(zhì)因數(shù)相乘，其結(jié)果作為給定數(shù)字的最大公約數(shù)。,算法(Algorithm)-例子,程序(Program),程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(4)。例如操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)

9、中執(zhí)行的程序，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。,算法的深入理解,算法的每一個(gè)步驟都必須沒(méi)有歧義，不能有半點(diǎn)含糊。必須認(rèn)真確定算法所處理的輸入的值域。同一算法可以用幾種不同的形式來(lái)描述。同一問(wèn)題，可能存在幾種不同的算法。針對(duì)同一問(wèn)題的算法可能會(huì)基于完全不同的解題思路，而且解題速度也會(huì)有顯著不同。,算法的應(yīng)用,人類基因項(xiàng)目

10、：找出人類DNA中的所有100 000種基因，確定構(gòu)成人類DNA的30億種化學(xué)基對(duì)的各種序列，將這些信息存儲(chǔ)在數(shù)據(jù)庫(kù)中，并開(kāi)發(fā)出用于進(jìn)行這方面數(shù)據(jù)分析的工具。因特網(wǎng)：好的傳輸路徑、搜索引擎電子商務(wù)制造業(yè)和其他商業(yè)應(yīng)用：最大化預(yù)期效益,2)建立數(shù)學(xué)模型,1)問(wèn)題的陳述,3)算法設(shè)計(jì),4)算法的正確性證明,5)算法的程序?qū)崿F(xiàn),6)算法分析,用科學(xué)規(guī)范的語(yǔ)言,對(duì)所求解的問(wèn)題做準(zhǔn)確的描述.,通過(guò)對(duì)問(wèn)題的分析,找出其中的所有操作對(duì)象及操作對(duì)

11、象之間的關(guān)系并用數(shù)學(xué)語(yǔ)言加以描述.,根據(jù)數(shù)學(xué)模型設(shè)計(jì)問(wèn)題的計(jì)算機(jī)求解算法.,證明算法對(duì)一切合法輸入均能在有限次計(jì)算后產(chǎn)生正確輸出.,對(duì)執(zhí)行該算法所消耗的計(jì)算機(jī)資源進(jìn)行估算.,將算法正確地編寫成機(jī)器語(yǔ)言程序.,問(wèn)題求解(Problem Solving),問(wèn)題求解(Problem Solving),理解問(wèn)題,精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略,設(shè)計(jì)算法,,,,,,,,,,,,,,,,算法設(shè)計(jì)與分析的步驟,算法一般分兩類：精確算法：

12、一個(gè)精確算法（exact algorithm）總能保證求得問(wèn)題的解。啟發(fā)式算法：一個(gè)啟發(fā)式算法（heuristic algorithm）通過(guò)使用某種規(guī)則、簡(jiǎn)化或智能猜測(cè)來(lái)減少問(wèn)題求解時(shí)間。,算法設(shè)計(jì)與分析的步驟,1.如何設(shè)計(jì)算法分治/遞歸動(dòng)態(tài)規(guī)劃貪心算法回溯法分支限界法概率算法,算法設(shè)計(jì)與分析的步驟,2.如何表示算法自然語(yǔ)言流程圖偽代碼程序設(shè)計(jì)語(yǔ)言,算法的描述方法自然語(yǔ)言優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、二義性使用

13、方法：粗線條描述算法思想注意事項(xiàng)：避免寫成自然段歐幾里德算法：①輸入m和n； ②求m除以n的余數(shù)r； ③若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第④步； ④將n的值放在m中，將r的值放在n中； ⑤重新執(zhí)行第②步。,算法設(shè)計(jì)與分析的步驟,流程圖優(yōu)點(diǎn)：流程直觀缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡(jiǎn)單算法注意事

14、項(xiàng)：注意抽象層次 歐幾里德算法：,算法設(shè)計(jì)與分析的步驟,程序設(shè)計(jì)語(yǔ)言優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù)歐幾里德算法：,#includeint CommonFactor(int m, int n){ int r = m % n; while (r!=0) { m = n; n = r; r

15、 = m % n; } return n;},算法設(shè)計(jì)與分析的步驟,偽代碼 介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的方法，它采用某一程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法，操作指令可以結(jié)合自然語(yǔ)言來(lái)設(shè)計(jì)。優(yōu)點(diǎn)：表達(dá)能力強(qiáng)、抽象性強(qiáng)、容易理解歐幾里德算法：1. r = m % n; 2. 循環(huán)直到r = 0;

16、2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 輸出n;,算法設(shè)計(jì)與分析的步驟,算法設(shè)計(jì)與分析的步驟,如何確認(rèn)算法如果一個(gè)算法對(duì)于所有合法的輸入，都能在有限時(shí)間內(nèi)輸出預(yù)期的結(jié)果，那么此算法是正確的。確認(rèn)一個(gè)算法是

17、否正確的活動(dòng)稱為算法確認(rèn)（algorithm validation）。算法確認(rèn)的目的在于確認(rèn)一個(gè)算法能否正確無(wú)誤地工作。使用數(shù)學(xué)方法證明算法的正確性，稱為算法證明（algorithm proof）。對(duì)于有些算法，正確性證明十分簡(jiǎn)單，但對(duì)于另一些算法，卻可能十分困難。,算法設(shè)計(jì)與分析的步驟,算法理論正確，但設(shè)計(jì)出的算法并不正確,例1:已知A=1012 B=-1012 C=1，計(jì)算A+B+C的值計(jì)算方法有兩個(gè)：A+B+C=1

18、 A+C+B=0,出現(xiàn)上述情況原因：使用工具只能表示七位，即計(jì)算機(jī)的精度問(wèn)題,例2：求解方程x2-（1015+1）*x+1015=0的根,A=1 B= 1015+1 C= 1015D=SQRT(B*B-4*A*C)X1=(-B+D)/(2*A)X2=(-B-D)(2*A),輸出結(jié)果：x1= 1015 X2=0,改

19、進(jìn)算法：使用韋達(dá)定理 X2=C/(2*X1),避免兩個(gè)大數(shù)相減,算法設(shè)計(jì)與分析的步驟,算法設(shè)計(jì)與分析的步驟,如何分析算法算法的分析（algorithm analysis）活動(dòng)是指對(duì)算法的執(zhí)行時(shí)間和所需空間的估算。分析算法要從它的三個(gè)性態(tài)考慮，即最好性態(tài)、最壞性態(tài)和平均性態(tài)。,分析算法的基本原則,正確性定義：在給定有效輸入后，算法經(jīng)過(guò)有限時(shí)間的計(jì)算并產(chǎn)生正確的答案，就稱算法是正確的。正確性證明

20、的內(nèi)容：方法的正確性證明——算法思路的正確性。證明一系列與算法的工作對(duì)象有關(guān)的引理、定理以及公式。程序的正確性證明——證明所給出的一系列指令確實(shí)做了所要求的工作。,分析算法的基本原則,工作量——時(shí)間復(fù)雜性分析計(jì)量工作量的標(biāo)準(zhǔn): 對(duì)于給定問(wèn)題，該算法所執(zhí)行的基本運(yùn)算的次數(shù)?；具\(yùn)算的選擇：根據(jù)問(wèn)題選擇適當(dāng)?shù)幕具\(yùn)算。,分析算法的基本原則,占用空間——空間復(fù)雜性分析兩種占用：存儲(chǔ)程序和輸入數(shù)據(jù)的空間存儲(chǔ)中間結(jié)果或操作單元所占用

21、空間——額外空間影響空間的主要因素：存儲(chǔ)程序的空間一般是常數(shù)(和輸入規(guī)模無(wú)關(guān))輸入數(shù)據(jù)空間為輸入規(guī)模O(n)空間復(fù)雜性考慮的是額外空間的大小如果額外空間相對(duì)于輸入規(guī)模是常數(shù)，稱為原地工作的算法。,分析算法的基本原則,簡(jiǎn)單性含義：算法簡(jiǎn)單，程序結(jié)構(gòu)簡(jiǎn)單。好處：容易驗(yàn)證正確性便于程序調(diào)試簡(jiǎn)單的算法效率不一定高。要在保證一定效率的前提下力求得到簡(jiǎn)單的算法。,分析算法的基本原則,最優(yōu)性含義：指求解某類問(wèn)題中效率最高的算法

22、兩種最優(yōu)性（設(shè)A是解某個(gè)問(wèn)題的算法）最壞情況：如果在解這個(gè)問(wèn)題的算法類中沒(méi)有其它算法在最壞情況下的時(shí)間復(fù)雜性比A在最壞情況下的時(shí)間復(fù)雜性低，則稱A是解這個(gè)問(wèn)題在最壞情況下的最優(yōu)算法。平均情況：如果在解這個(gè)問(wèn)題的算法類中沒(méi)有其它算法在平均情況下的時(shí)間復(fù)雜性比A在平均情況下的時(shí)間復(fù)雜性低，則稱A是解這個(gè)問(wèn)題在平均情況下的最優(yōu)算法。,分析算法的基本原則,例：在n個(gè)不同的數(shù)中找最大的數(shù)。算法：Find_Max輸入：數(shù)組L，項(xiàng)數(shù) n

23、輸出：L中的最大項(xiàng)MAXMAX←L(1); i←2;while i≤n doif MAX<L(i) then MAX←L(i);i←i+1;end。定理：在n個(gè)數(shù)的數(shù)組中找最大的數(shù)，并以比較作為基本運(yùn)算的算法類中的任何算法最壞情況下至少要做n－1次比較。結(jié)論：Find_Max算法是最優(yōu)算法。,算法設(shè)計(jì)的要求,正確性：4個(gè)層次可讀性：有助于對(duì)算法的理解（結(jié)構(gòu)化、模塊化、加注釋等）健壯性：輸入數(shù)據(jù)非法，作出適當(dāng)反應(yīng)或

24、進(jìn)行處理高效率與低存儲(chǔ)要求：效率是指算法執(zhí)行的時(shí)間,通常設(shè)計(jì)一個(gè)“好”的算法應(yīng)考慮達(dá)到以下目標(biāo)：,算法復(fù)雜性分析,算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問(wèn)題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)

25、雜性分開(kāi)，并分別用T和S來(lái)表示，則有： T=T(N,I)和S=S(N,I) 。（通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中）,算法復(fù)雜性分析,算法復(fù)雜性（Algorithm Analysis） = 算法所需要的計(jì)算機(jī)資源=時(shí)間+空間依賴于求解問(wèn)題的規(guī)模、算法的輸入和算法本身的函數(shù)。C=F(N,I,A)，其中，C表示復(fù)雜性，N表示求解問(wèn)題的規(guī)模，I表示算法的輸入，A表示算法本身算法的時(shí)間復(fù)雜性（Time Complexity）T(N) ≈

26、 T(N,I,A) ≈ T(N,I) ；算法的空間復(fù)雜性（Space Complexity）S(N) ≈ S(N,I,A) ≈ S(N,I) 。其中N是問(wèn)題的規(guī)模（輸入大?。?算法復(fù)雜性分析,算法分析的目的： 設(shè)計(jì)算法——設(shè)計(jì)出復(fù)雜性盡可能低的算法 選擇算法——在多種算法中選擇其中復(fù)雜性最低者,算法的時(shí)間復(fù)雜性,因?yàn)椴豢赡軐?duì)規(guī)模為N的每一種合法的輸入I都統(tǒng)計(jì)，所以只能在規(guī)模為N的某些代表性的合法輸入中考慮時(shí)間復(fù)雜性：（1

27、）最壞情況下的時(shí)間復(fù)雜性 Tmax(N) =（2）最好情況下的時(shí)間復(fù)雜性 Tmin(N) =（3）平均情況下的時(shí)間復(fù)雜性 Tavg(N) = 是算法的應(yīng)用中出現(xiàn)輸入I的概率 其中： 是規(guī)模為N的合法輸入的集合； 是 中使 達(dá)到Tmax(N) 的合法輸入； 是 中使

28、 達(dá)到Tmin(N) 的合法輸入,,可操作性最好且最有實(shí)際價(jià)值?。。?算法的時(shí)間復(fù)雜性,例：順序搜索算法,templateint seqSearch(Type *a, int n, Type k){ for(int i=0;i<n;i++) if (a[i]==k) return i; return -1;},在具有n個(gè)元素的數(shù)組a[1...n]中找出值等于k的元素的位置。,算

29、法的時(shí)間復(fù)雜性,（1）Tmax(n) = max{ T(I) | size(I)=n }=n（2）Tmin(n) = min{ T(I) | size(I)=n }=1（3）在平均情況下，假設(shè)： (a) 搜索成功的概率為p ( 0 ? p ? 1 )； (b) 在數(shù)組的每個(gè)位置i ( 0 ? i < n )搜索成功的概率相同，均為 p/n。,,,,,1). 賦值,比較,算術(shù)運(yùn)算,邏輯運(yùn)算,讀寫單個(gè)變量(常量)只需1

30、單位時(shí)間 2). 執(zhí)行條件語(yǔ)句 if c then S1 else S2 的時(shí)間為TC +max(TS1,TS2). 3). 選擇語(yǔ)句 case A of a1: s1；a2: s2；...； am: sm 需要的時(shí)間為 max（TS1,TS2 ,..., TSm）. 4). 訪問(wèn)數(shù)組的單個(gè)分量或記錄的單個(gè)域需要一個(gè)單位時(shí)間. 5). 執(zhí)行for循環(huán)語(yǔ)句的時(shí)間=執(zhí)行循環(huán)體時(shí)間*循環(huán)次數(shù). 6). while

31、c do s (repeat s until c)語(yǔ)句時(shí)間=(Tc+Ts)*循環(huán)次數(shù). 7). 用goto從循環(huán)體內(nèi)跳到循環(huán)體末或循環(huán)后面的語(yǔ)句時(shí),不需額外時(shí)間 8). 對(duì)非遞歸調(diào)用,根據(jù)調(diào)用層次由里向外用規(guī)則1-7進(jìn)行分析； 對(duì)遞歸調(diào)用,可建立關(guān)于T(n)的遞歸方程,求解該方程得到T(n).,時(shí)間復(fù)雜性分析的規(guī)則:(最壞情況),例：求n階行列式的值,一個(gè)n階行列式應(yīng)該做n!(n-1)次乘法。若每個(gè)乘法運(yùn)算的時(shí)間是10

32、-6 s，則求n階行列式之所用的時(shí)間為,T(n)=n!*(n-1)*10 -6 s,當(dāng)n=10時(shí)，T(10)=32.65s當(dāng)n=50時(shí)，T(50)=4.7*1052y（年）,當(dāng)問(wèn)題的規(guī)模越來(lái)越大時(shí)，求解它所需要的時(shí)間和空間的增長(zhǎng)率，也就是把時(shí)間和空間的增長(zhǎng)率作為衡量算法的標(biāo)準(zhǔn)。,算法漸近復(fù)雜性,算法漸近復(fù)雜性,假設(shè)T(N) 是關(guān)于算法A的復(fù)雜性函數(shù)T(N) ?? , 當(dāng) N?? ;存在 ， (T(N) -

33、 ) / T(N) ?0 ，當(dāng) N??; 是T(N)的漸近性態(tài)，為算法的漸近復(fù)雜性。在數(shù)學(xué)上， 是T(N)的漸近表達(dá)式，是T(N)略去低階項(xiàng)留下的主項(xiàng)。它比T(N) 簡(jiǎn)單?；貞浬蠈W(xué)期的例子：省去系數(shù)項(xiàng)！?。?T(N) ≈ T(N,I,A),算法漸近復(fù)雜性,例如：設(shè)T(n)=3n2+4nlogn+7 是算法A的復(fù)雜性函數(shù) =3n2 漸近于T(n)嗎

34、？,as n??(T(n) - )/ T(n)=4nlogn+7/ 3n2+4nlogn+7 ?0,當(dāng)n趨近無(wú)窮時(shí)， T(n)漸近于 ，所以可以用 替代T(n)作為算法A在n??時(shí)的時(shí)間復(fù)雜性的度量。,算法漸近復(fù)雜性,若進(jìn)一步假定算法中所有不同元運(yùn)算的單位執(zhí)行時(shí)間相同,則可不考慮?(n)所包含的系數(shù)或常數(shù)因子。,漸進(jìn)分析適用于n充分大的情況,當(dāng)問(wèn)題的規(guī)模很小時(shí),或比較的兩算法同階時(shí),則不能做這種簡(jiǎn)化.

35、,如果對(duì)某一常數(shù)C，一個(gè)算法在時(shí)間Cn2內(nèi)能處理尺度為n的輸入，則稱此算法的時(shí)間復(fù)雜性是O(n2)。,漸近分析的記號(hào),在下面的討論中，對(duì)所有N，f(N) ? 0，g(N) ? 0。（1）漸近上界記號(hào)OO(g(N)) = { f(N) | 存在正常數(shù)C和N0使得對(duì)所有N? N0有：0 ? f(N) ? Cg(N) }說(shuō)明：函數(shù)f(N) 當(dāng)N充分大時(shí)上有界， g(N) 是它的一個(gè)上界，記為f(N)= O(g(N))，f(N) 的階不高

36、于g(N)的階,漸近分析的記號(hào),（1）漸近上界記號(hào)O—實(shí)例當(dāng)N ?1時(shí)，有3N ? 4N,所以有3N=O(N);當(dāng)N ?1時(shí)，有N+1024 ? 1025N,所以有N+1024=O(N);當(dāng)N ?10時(shí)，有2N2+11N-10 ? 3N2,所以有2N2+11N-10=O(N2);當(dāng)N ?1時(shí)，有N2 ? N3,所以有N2 =O(N3);N3≠O(N2),一般地，對(duì)于足夠大的n，常用的時(shí)間復(fù)雜性存在以下順序： O(1)<

37、 O(logn)< O(n)< O(n*logn)<O(n2)<O(n3)…<O(2n)<O(3n)<…<O(n!),典型的計(jì)算時(shí)間函數(shù)的增長(zhǎng)情況,漸近分析的記號(hào),例：順序搜索算法,templateint seqSearch(Type *a, int n, int x){ for(int i=0;i<n;i++) if (a[i]==x) return i;

38、 return -1;},在平均情況下，假設(shè)： (a) 搜索成功的概率為p ( 0 ? p ? 1 )； (b) 在數(shù)組的每個(gè)位置i ( 0 ? i < n )搜索成功的概率相同，均為 p/n。,（1）Tmax(n) = max{ T(I) | size(I)=n }=O(n)（2）Tmin(n) = min{ T(I) | size(I)=n }=O(1)（3）Tavg(n) =,要求:求出最壞、最好和平均情況下

39、的時(shí)間復(fù)雜度？,漸近分析的記號(hào),Tmax(n) =n Tmin(n) =1,漸近分析的記號(hào),如何分析算法復(fù)雜度？,1、分析算法的工作量—忽略（細(xì)節(jié)）次要工作量，留下主要工作量（主要運(yùn)算），從而分析其趨勢(shì),2、基本運(yùn)算—主要工作是哪方面尋找規(guī)則：基本運(yùn)算的次數(shù)和算法總運(yùn)算次數(shù)成比例關(guān)系；基本運(yùn)算以外的其他運(yùn)算可以忽略,3、算法復(fù)雜度還和問(wèn)題規(guī)模n有關(guān)，如順序查找T(n)=n,算法分析的基本法則,非遞歸算法：（1）for / whil

40、e 循環(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í)間的較大者。,例 templatevoid insertion_sort(Type *a, int n){ Type key; // cost

41、times for (int i = 1; i =0 && a[j]>key ){ // c4 sum of ti a[j+1]=a[j]; // c5 sum of (ti-1) j--;

42、 // c6 sum of (ti-1) } a[j+1]=key; // c7 n-1 }},,,,1、在最好情況下，ti=1, for 1 ? i <n;,2、在最壞情況下，ti ? i+1, for 1 ? i <n;,輸入數(shù)據(jù)a[i]=n-i,

43、 i=0,1,…,n-1,遞歸算法復(fù)雜性分析,int factorial(int n) { if (n == 0) return 1; return n*factorial(n-1); },漸近分析的記號(hào),規(guī)則O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的證明：對(duì)于任意f1(n) ? O(f(n)) ，存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有n? n1

44、，有f1(n) ? c1f(n) 。類似地，對(duì)于任意g1(n) ? O(g(n)) ，存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有n? n2，有g(shù)1(n) ? c2g(n) 。令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。則對(duì)所有的 n ? n3，有f1(n) +g1(n) ? c1f(n) + c2g(n) ? c3f(n) + c3g(n)= c3(f(n)

45、 + g(n)) ? c32 max{f(n),g(n)} = 2c3h(n) = O(max{f(n),g(n)}) .,漸近分析的記號(hào),在下面的討論中，對(duì)所有N，f(N) ? 0，g(N) ? 0。（2）漸近下界記號(hào)? ? (g(N)) = { f(N) | 存在正常數(shù)C和N0使得對(duì)所有N? N0有：0? cg(N) ? f(N) }說(shuō)明：函數(shù)f(N) 當(dāng)N充分大時(shí)下有界， g(N) 是它的一個(gè)下界，記為f(N

46、) =? (g(N)) ， f(N) 的階不低于g(N)的階,（3）非緊上界記號(hào)o o(g(n)) = { f(n) | 對(duì)于任何正常數(shù)c>0，存在正數(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(

47、n)),（5）緊漸近界記號(hào)? ? (g(n)) = { f(n) | 存在正常數(shù)c1,c2和n0使得對(duì)所有n? n0有：c1g(n) ? f(n) ? c2g(n) } 定理1： ? (g(n)) = O (g(n)) ? ? (g(n)),漸近分析記號(hào)在等式和不等式中的意義,f(n)= ?(g(n))的確切意義是：f(n) ? ?(g(n))。一般情況下，等式和不等式中的漸近記號(hào)?(g(n))表示?(g(n))中的某個(gè)函數(shù)。

48、例如：2n2 + 3n + 1 = 2n2 + ?(n) 表示 2n2 +3n +1=2n2 + f(n)，其中f(n) 是?(n)中某個(gè)函數(shù)。等式和不等式中漸近記號(hào)O,o, ?和?的意義是類似的。,漸近分析中函數(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.,漸近分析記號(hào)的若干性質(zhì),（1）傳遞

49、性：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)= ?

50、(h(n)) ? f(n)= ? (h(n))；,（2）反身性：f(n)= ?(f(n))；f(n)= O(f(n))；f(n)= ?(f(n)).（3）對(duì)稱性：f(n)= ?(g(n)) ? g(n)= ? (f(n)) .（4）互對(duì)稱性：f(n)= O(g(n)) ? g(n)= ? (f(n)) ；f(n)= o(g(n)) ? g(n)= ? (f(n)) ；,（5）算術(shù)運(yùn)算：O(f(n))+O(g(n))

51、= O(max{f(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)) 。,算法漸近復(fù)雜性分析中常用函數(shù),（1）單調(diào)函數(shù)單調(diào)遞增：m ? n ? f(m) ? f(n) ;單調(diào)遞減：m ? n ? f(m)

52、 ? f(n);嚴(yán)格單調(diào)遞增：m f(n).（2）取整函數(shù) ? x ? ：不大于x的最大整數(shù)； ? x ? ：不小于x的最小整數(shù)。,取整函數(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

53、 ? 為單調(diào)遞增函數(shù)。,（3）多項(xiàng)式函數(shù) p(n)= a0+a1n+a2n2+…+adnd； ad>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) ;k < d ? p(n) = ?(nk)

54、 .,（4）指數(shù)函數(shù) 對(duì)于正整數(shù)m,n和實(shí)數(shù)a>0: a0=1; a1=a ; a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n ; a>1 ? an為單調(diào)遞增函數(shù); a>1 ? ? nb = o(an),,ex ? 1+x;|x| ?1 ? 1+x ? ex ? 1+x+x2 ; ex = 1+x+

55、 ?(x2), as x?0;,,,（5）對(duì)數(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>0,,,,,,,,|x| ?1 ?for x > -1,for any a > 0,

56、 , ? logbn = o(na),,,,（6）階層函數(shù)Stirling’s approximation,,,,,,,,,算法分析中常見(jiàn)的復(fù)雜性函數(shù),小規(guī)模數(shù)據(jù),中等規(guī)模數(shù)據(jù),用C++描述算法,（1）選擇語(yǔ)句：（1.1) if 語(yǔ)句：（1.2) ？語(yǔ)句：,if (expression) statement;else statement;,exp1?exp2:exp3

57、 y= x>9 ? 100:200; 等價(jià)于： if (x>9) y=100; else y=200;,（1.3) switch語(yǔ)句：,,switch (expression) { case 1: statement sequence; break; case 2: statement sequence; break; ?

58、 default: statement sequence; },（2）迭代語(yǔ)句：,（2.1) for 循環(huán)： for (init;condition;inc) statement;（2.2) while 循環(huán)： while (condition) statement;（2.3) do-while 循環(huán)： do{ statement; } while (condition);,（3）跳

59、轉(zhuǎn)語(yǔ)句：,（3.1) return語(yǔ)句： return expression;（3.2) goto語(yǔ)句： goto label; ? label:,（4）函數(shù)：,例：,return-type function name(para-list){ body of the function },int max(int x,int y) { return x>y?x:y; },（5）模板t

60、emplate ：,template Type max(Type x,Type y){ return x>y?x:y;} int i=max(1,2)；double x=max(1.0,2.0)；,（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 ?

61、y=new int；?y=10；或 int ?y=new int(10)；或 int ?y；y=new int(10)；,（6.2）一維數(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 float[n]；創(chuàng)建一個(gè)大小為n的一維浮點(diǎn)數(shù)組。運(yùn)算符new分配n個(gè)浮點(diǎn)數(shù)所需的空間，并返回指向第一個(gè)浮點(diǎn)數(shù)的指針。然后

62、可用x[0]，x[1]，…，x[n-1]來(lái)訪問(wèn)每個(gè)數(shù)組元素。,（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的空間。,（6.4）動(dòng)態(tài)二維數(shù)組 ：,創(chuàng)建類型為Type的動(dòng)態(tài)工作數(shù)組，這個(gè)數(shù)組有rows行和cols列。,template void Mak

63、e2DArray(Type** &x,int rows, int cols){ x=new Type*[rows]; for (int i=0;i<rows;i++) x[i]=new Type[cols];},當(dāng)不再需要一個(gè)動(dòng)態(tài)分配的二維數(shù)組時(shí)，可按以下步驟釋放它所占用的空間。首先釋放在for循環(huán)中為每一行所分配的空間。然后釋放為行指針?lè)峙涞目臻g。