第二章算法的構(gòu)造及評(píng)價(jià)

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

1.模型化

對(duì)實(shí)際問(wèn)題進(jìn)行分析，選擇適當(dāng)?shù)臄?shù)學(xué)模型來(lái)描述問(wèn)題，即模型化。

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

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

4.ADT的實(shí)現(xiàn)對(duì)每個(gè)ADT，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)表示數(shù)學(xué)模型，并用相應(yīng)的函數(shù)實(shí)現(xiàn)每個(gè)操作。第三頁(yè)，共三十頁(yè)，編輯于2023年，星期四算法逐步求精實(shí)例例2.1.2交叉路口的交通安全管理問(wèn)題DCBAE圖2.1一個(gè)交叉路口問(wèn)題描述

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

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

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

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

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

v=G中第一個(gè)未著色的頂點(diǎn)；

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

w=newclr中的第一個(gè)頂點(diǎn)；

while(w!=0){/*newclr中的頂點(diǎn)還沒(méi)取盡*/

if(v與w相鄰)

found=1;

w=newclr中的下個(gè)頂點(diǎn)；};

if(found==0){

對(duì)v著色；將v放入newclr；};v=G中下一個(gè)未著色的頂點(diǎn)；}};第十一頁(yè)，共三十頁(yè)，編輯于2023年，星期四第四步求精引入ADT

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

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

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

*說(shuō)明，對(duì)于一個(gè)為和式的累加次數(shù)，其時(shí)間復(fù)雜性僅取決于該式中最高階項(xiàng)的階，而與該最高階項(xiàng)的系數(shù)和其他低階項(xiàng)無(wú)關(guān)。常見(jiàn)的時(shí)間復(fù)雜性有：О（1）<О（㏒㏒n）<О（㏒n）<О（n）<О（n㏒n）<О（n2）<О（n3）<О（2n）第二十一頁(yè)，共三十頁(yè)，編輯于2023年，星期四2.2.2算法時(shí)間復(fù)雜性分析方法各類時(shí)間復(fù)雜性的直觀比較（圖形化）T(n)n01000200030005101520252nn3100n5n2logn2100△n△

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

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)第二十四頁(yè)，共三十頁(yè)，編輯于2023年，星期四算法時(shí)間復(fù)雜性分析實(shí)例(1)例2A是一個(gè)由n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出求最大元和最小元的s算法SM時(shí)間復(fù)雜性。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的基本操作為兩個(gè)判斷及賦值語(yǔ)句，基于循環(huán)結(jié)構(gòu)的分析T(n)=O(1)+2（n-1）=O(n)第二十五頁(yè)，共三十頁(yè)，編輯于2023年，星期四算法時(shí)間復(fù)雜性分析實(shí)例(2)例3：Longfact

(intn)

{if(n==0)||(n==1)return(1);elsereturn(n*fact(n–1));}T(n)=C當(dāng)n=0,n=1G+T(n–1)當(dāng)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)第二十六頁(yè)，共三十頁(yè)，編輯于2023年，星期四算法時(shí)間復(fù)雜性分析實(shí)例(3)例4

A是一個(gè)由n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出確定實(shí)數(shù)K是否在A中的算法SK的時(shí)間復(fù)雜性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中}注：此時(shí)，執(zhí)行次數(shù)除了依賴于問(wèn)題的規(guī)模（數(shù)組A的