第二章算法的構造及評價

第二章算法的構造及評價哈工大計算機科學與技術學院數(shù)據(jù)結構課程組1第一頁，共三十頁，2022年，8月28日2.1逐步求精的算法構造過程2.1.1算法的定義1.計算能由一個給定的計算模型機械地執(zhí)行的規(guī)則(或步驟)序列稱為該計算模型的一個計算.注:一個計算機程序是一個計算(計算模型是計算機);計算可能永遠不停止—不是算法.2.算法是一個滿足下列條件的一個計算（程序）：(1)有窮性/終止性：總是在執(zhí)行有窮步后停止;(2)確定性：每一步必須有嚴格的定義和確定的動作;(3)能行性：每個動作都能被精確地機械執(zhí)行;(4)輸入：有0個和多個滿足約束條件的輸入;(5)輸出：有一個或多個滿足約束條件的結果.第二頁，共三十頁，2022年，8月28日2.1.2算法構造過程實際上就是用計算機求解一個問題的過程

1.模型化

對實際問題進行分析，選擇適當?shù)臄?shù)學模型來描述問題，即模型化。

2.確定解決思路根據(jù)模型，找出解決問題的思路方法(算法的原型，一般用自然語言描述)。

3.逐步求精對用自然語言等描述的算法逐步細致化、精確化和形式化。這一階段可能包括多個步驟。當?shù)竭_適當精度時，許多非形式的描述可轉(zhuǎn)變?yōu)榛贏DT的形式化描述。

4.ADT的實現(xiàn)對每個ADT，選擇適當?shù)臄?shù)據(jù)結構表示數(shù)學模型，并用相應的函數(shù)實現(xiàn)每個操作。第三頁，共三十頁，2022年，8月28日算法逐步求精實例例2.1.2交叉路口的交通安全管理問題DCBAE圖2.1一個交叉路口問題描述

一個具有多有多條通路的交叉路口,當允許某些通路上的車輛在交叉路口“拐彎”時,必須對其他一些通路上的車輛加以限制,不允許同時在交叉路口“拐彎”,以免發(fā)生碰撞.問題要求

(1)設置一組交通燈,實現(xiàn)安全管理（無碰撞管理）.(2)使交通燈的數(shù)目最少.第四頁，共三十頁，2022年，8月28日問題的分析所有這些可能的“拐彎”構成一個集合.將此集合分成組,使得每組中所有的“拐彎”都能同時進行而不發(fā)生碰撞.每組對應一個指揮燈,保證不碰撞;用盡可能少的指揮燈歸結為分成盡可能少的組.問題歸結為如何進行集合的劃分？第五頁，共三十頁，2022年，8月28日模型化(1)用圖作為交叉路口的數(shù)學模型;(2)每個“拐彎”對應圖中的一個頂點;(3)若兩個“拐彎”不能同時進行,則用用一條邊把這兩個“拐彎”所對應的兩個結點連接起來，并且說這兩個頂點是相鄰的。ABACADBADCEDBCBDEADADBEBECDCBAE一個交叉路口第六頁，共三十頁，2022年，8月28日算法的基本思路轉(zhuǎn)化為圖的著色問題（著同一顏色的結點即為一組）。常見算法為（1）窮舉法（2）試探法（3）貪心法“貪心”算法的基本思想是首先用第一種顏色對圖中盡可能多的頂點著色(盡可能多表現(xiàn)出“貪心”)，然后用第二種顏色對余下的頂點中盡可能多的頂點著色，如此等等，直至所有的頂點都著完色。第七頁，共三十頁，2022年，8月28日算法原型（自然語言描述）（1）將所有的結點設置為未著色（2）當有未著色的結點時，進行如下步驟（3）產(chǎn)生一種新的顏色（4）選取某個未著色的點，用此新顏色對其著色（5）掃描所有未著色的頂點，對其中的每個頂點盡可能的用此新顏色著色。（依據(jù)為它是否與已著新顏色的任何頂點相鄰。若不相鄰，則用新顏色對它著色。）（此處體現(xiàn)了貪心）。（6）重復步驟（2）-（5），直到所有的結點均以著色第八頁，共三十頁，2022年，8月28日第一步求精（偽代碼描述）

voidgreedy(G,newclr)GRAPHG;SETnewclr;/*類型GRAPH和SET有待具體說明*//*本程序把G中可以著同一色的頂點放入newclr*/{(1)newclr=

(2)for(G中所有未著色的頂點v)(3)if(v不與newclr中的任何頂點相鄰){(4)對v著色；(5)將v放入newclr；}};

voidColor(G)GRAPHG;/*類型GRAPH有待具體說明*/{SETclr;clr=;while(G中有未著色的頂點){SETnewclr=new(SET);/*產(chǎn)生一種新顏色*/greedy(G,newclr);/*用此新顏色對盡可能多的結點進行著色*/將newclr放入clr;}};算法Color(G)完成對圖G的著色，其執(zhí)行結果為clr集合，它即為頂點集的一個劃分。其中的每個元素為著相同顏色的頂點集。第九頁，共三十頁，2022年，8月28日第二步求精求精v不與newclr中的任何頂點相鄰（即對于所有的頂點，都不相鄰）voidgreedy(G,newclr)GRAPHG;SETnewclr;{intfound;(1)newclr=;(2)for(G中所有未著色的頂點v){(3.1)found=0;/*found的初值為false*/(3.2)for(newclr中的每一個頂點w）(3.3)if(v與w相鄰)(3.4)found=1;(3.5)if(found==0){/*v與newclr中的任何頂點都不相鄰*/(4)對v著色；(5)將v放入newclr；}}};第十頁，共三十頁，2022年，8月28日第三步求精遍歷集合中的所有頂點voidgreedy(GRAPHG,SETnewclr){intfound;newclr=;

v=G中第一個未著色的頂點；

while(v!=0){/*G中還有未著色的頂點v*/found=0;

w=newclr中的第一個頂點；

while(w!=0){/*newclr中的頂點還沒取盡*/

if(v與w相鄰)

found=1;

w=newclr中的下個頂點；};

if(found==0){

對v著色；將v放入newclr；};v=G中下一個未著色的頂點；}};第十一頁，共三十頁，2022年，8月28日第四步求精引入ADT

根據(jù)上一步求精的結果，算法中大部分操作都歸結為對圖和集合的操作。因此需定義ADTGRAPH和ADTSET。設G為GRAPH的實例，則需在G上定義如下操作： (1)FIRSTG(G)返回G中的第一個未加標記的（未著色的）元素；若G中沒有這樣的元素存在，則返回NULL。 (2)EDGE(v,w,G)若v和w在G中相鄰，則返回true，否則返回false。 (3)MARK(v,G)標記G中的元素v。 (4)ADDG(v,G)將元素v放入G中。 (5)NEXTG(G)返回G中下一個未標記的元素，若G中沒有這樣的元素存在，則返回NULL。設S為SET的實例，則需在S上在定義如下操作：(1)MAKENULL(S)將集合S置空。(2)FIRST(S)返回S中的第一個元素；若S為空集，則返回NULL。(3)NEXT(S)返回S中的下一個元素；若S中沒有下一個元素，則返回NULL。 (4)ADDS(v,S)將v放入S中第十二頁，共三十頁，2022年，8月28日第五步求精用引入的ADT對算法進行形式化描述voidgreedy(G,newclr)GRAPHG;SETnewclr;{

intfound;elementtypev,w;/*elementtype可以自定義*/

MAKENULL(newclr);v=FIRSTG(G);while(v!=NULL){found=0;w=FIRST(newclr);while(w!=NULL){if(EDGE(v,w,G))found=1;w=NEXT(newclr);};v=NEXTG(G);}};第十三頁，共三十頁，2022年，8月28日第六步求精ADT的實現(xiàn)以及整個程序的連編確定抽象數(shù)據(jù)型GRAPH及SET的數(shù)據(jù)模型如何實現(xiàn)。編寫相應的操作函數(shù)。給出類型elementtype的定義和實現(xiàn)。將各部分連在一起。第十四頁，共三十頁，2022年，8月28日2.2算法評價和復雜性分析2.2.1算法的評價準則算法時間復雜性分析方法第十五頁，共三十頁，2022年，8月28日2.2.1算法的評價準則一：正確性(Correctness)含義：指對一切合法的輸入數(shù)據(jù)經(jīng)有限時間或有限步后均可得到正確（滿足規(guī)格說明要求）的結果。算法的正確性證明常有兩種途徑：形式化證明先構造一組相關的引理和定理，再形式的證明語句系列確實完成了符合規(guī)定的正確動作。對于復雜的算法，其正確性的形式證明仍是一個有待突破的課題。驗證由于一切合法輸入可能是不可窮盡的，所以通常只是構造一些有代表性的輸入進行驗證（這是我們通常采取的辦法）。第十六頁，共三十頁，2022年，8月28日2.2.1算法的評價準則二：時間復雜性(TimeComplexity)含義：對于同一問題的不同正確算法，其執(zhí)行時間的多少成為又一評價準則。計算和比較算法的執(zhí)行時間常有兩種方法：實驗測量法（即計算其實際執(zhí)行時間或執(zhí)行的指令條數(shù)）優(yōu)點：精確。缺點：算法必須編制成可運行程序后才能進行比較；所得的結果過多的依賴于非算法本身的因素，如計算機的硬件、編譯程序、編程語言、操作系統(tǒng)等。數(shù)學分析法第十七頁，共三十頁，2022年，8月28日時間復雜性的數(shù)學分析可以進行數(shù)學分析算法的組成具有一定的規(guī)律：由一些基本操作經(jīng)過三種控制結構（順序，分支和循環(huán)）組成。就可以直接在程序的基礎上，分析得出這些基本操作的累加次數(shù)，基于這一次數(shù)就可比較算法執(zhí)行時間。時間復雜性的定義對于特定算法，其基本操作的累加次數(shù)只和問題的規(guī)模n有關，因此是一個關于n的函數(shù)，標記為T(n)。由于進行數(shù)學分析，主要考慮T(n)的增長率，變化趨勢及界限等，其具體數(shù)值意義不大；所以主要考慮的是基本操作的重復次數(shù)。定義：算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間復雜性定義為T(n)=O(f(n))。此處O表示T(n)至多與f(n)同階，因此也稱為漸進時間復雜度（f(n)是T(n)增長率的上界。第十八頁，共三十頁，2022年，8月28日2.2.1算法的評價準則三：空間復雜性(SpaceComplexity)含義：算法的空間復雜性是指算法在執(zhí)行過程中的存儲量需求。其存儲量需求主要包括：存放算法本身的指令、常數(shù)、變量和輸入數(shù)據(jù)數(shù)據(jù)進行操作的工作單元和存儲實現(xiàn)計算所需的輔助空間第二部分是主要的算法執(zhí)行的不同時刻，其空間需求可能不同，此處考慮其最大需求。定義：算法在執(zhí)行過程中的最大存儲量需求是關于問題規(guī)模n的某個函數(shù)f(n)，定義算法的空間復雜度為：S(n)=O(f(n))。第十九頁，共三十頁，2022年，8月28日2.2.1算法的評價準則四：可讀性(Readability)可讀性好的算法有助于設計者和和他人閱讀、理解、修改和重用晦澀難懂的算法不容易隱藏錯誤，而且還增加了閱讀…難度可讀性好的算法，常常也具有簡單性。五：健壯性(Robustness)含義：當輸入數(shù)據(jù)非法時，能作出適當?shù)姆磻ㄈ鐚斎霐?shù)據(jù)進行語法檢查，提出修改輸入建議并提供重新輸入的機會），避免異常出錯。六：靈活性（Flexibility）、可重用性(Reuseabale)和自適應性(Adaptability)等。第二十頁，共三十頁，2022年，8月28日2.2.2算法時間復雜性分析方法一：O的含義定義1

設f（n）、T（n）是整數(shù)集到實數(shù)集上的函數(shù)，稱函數(shù)f（n）是T（n）增長率的上界，當且僅當存在一個正常數(shù)C和整數(shù)n0，使得對任意的n≥n0時，有T(n)≤Cf(n)。記作：T（n）=O（f（n））此時也表明

T（n）的階至多為f（n））例1設函數(shù)T（n）=3n5+4n2+1，則T（n）=О（n5）證明：f（n）=n5.取n0=0,C=8,則當n≥n0時有T（n）=3n5+4n2+1≤8n5=Cf（n）證畢例推廣此例得：若A（n）=amnm+…+a1n+a0，則A（n）=О（nm）

*說明，對于一個為和式的累加次數(shù)，其時間復雜性僅取決于該式中最高階項的階，而與該最高階項的系數(shù)和其他低階項無關。常見的時間復雜性有：О（1）<О（㏒㏒n）<О（㏒n）<О（n）<О（n㏒n）<О（n2）<О（n3）<О（2n）第二十一頁，共三十頁，2022年，8月28日2.2.2算法時間復雜性分析方法各類時間復雜性的直觀比較（圖形化）T(n)n01000200030005101520252nn3100n5n2logn2100△n△

T(n)第二十二頁，共三十頁，2022年，8月28日2.2.2算法時間復雜性分析方法二：時間復雜性的運算法則對于單個語句，無論是賦值、判斷、加減等，都有T(n)=O(1)。復合結構（多條語句通過控制結構組合）的T(n)分析需應用如下法則：此處設T1(n)=O(f(n))，T2(n)=O(g(n))分別為程序段P1和P2的運行時間。加法規(guī)則（P1和P2順序連結）：T1(n)+T2(n)=O(max{f(n),g(n)})乘法規(guī)則（P1和P2嵌套連結）：T1(n)·T2(n)=O(f(n)·g(n))第二十三頁，共三十頁，2022年，8月28日2.2.2算法時間復雜性分析方法三：對三種控制結構進行時間復雜性分析順序結構：語句序列s1,…,sk的運行時間由加法原則確定：即T(s1,…,sk)=max{T(s1),…,T(sk)}分支結構：T(if(B)s1elses2)=T(B)+T(else)+max{T(s1),T(s2)}通常取T(B)+T(else)=O(1)循環(huán)結構：

T(for(i=1;i<=n;i++)s)=T(i=1)+(T(for)+T(i<=n)+T(i++)+T(s))通常取T(i=1)=O(1);T(for)+T(i<=n)+T(i++)=O(1)第二十四頁，共三十頁，2022年，8月28日算法時間復雜性分析實例(1)例2A是一個由n個不同元素的實數(shù)數(shù)組，給出求最大元和最小元的s算法SM時間復雜性。voidSM(doubleA[],intn,doublemax,doublemin){doublemax,min;max=min=A[0];for(k=1;k<=n-1;k++){if(A[k]>max)max=A[k];if(A[k]<min)min=A[k];}}容易看出，算法SM的基本操作為兩個判斷及賦值語句，基于循環(huán)結構的分析T(n)=O(1)+2（n-1）=O(n)第二十五頁，共三十頁，2022年，8月28日算法時間復雜性分析實例(2)例3：Longfact

(intn)

{if(n==0)||(n==1)return(1);elsereturn(n*fact(n–1));}T(n)=C當n=0,n=1G+T(n–1)當n>1

T(n)=G+f(n–1)T(n–1)=G

+f(n–2)T(n–2)=G

+f(n–3)……T(2)=G

+f(1)T(1)=C∴T(n)=G（n-1）+C∴T(n)=O(G(n-1)+C)=O(n)第二十六頁，共三十頁，2022年，8月28日算法時間復雜性分析實例(3)例4

A是一個由n個不同元素的實數(shù)數(shù)組，給出確定實數(shù)K是否在A中的算法SK的時間復雜性intSK(doubleA[],intn,doubleK){intj=1;while(j<=n){if(A[j]==K)break;elsej++;}returnj;//若j≤n，則K在A中，否則(j=n+1)K不在A中}注：此時，執(zhí)行次數(shù)除了依賴于問題的規(guī)模（數(shù)組A