第二章算法的構(gòu)造及評價_第1頁
第二章算法的構(gòu)造及評價_第2頁
第二章算法的構(gòu)造及評價_第3頁
第二章算法的構(gòu)造及評價_第4頁
第二章算法的構(gòu)造及評價_第5頁
已閱讀5頁,還剩25頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領

文檔簡介

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

1.模型化

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

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

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

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

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

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

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);/*用此新顏色對盡可能多的結(jié)點進行著色*/將newclr放入clr;}};算法Color(G)完成對圖G的著色,其執(zhí)行結(jié)果為clr集合,它即為頂點集的一個劃分。其中的每個元素為著相同顏色的頂點集。第九頁,共三十頁,編輯于2023年,星期四第二步求精求精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;}}};第十頁,共三十頁,編輯于2023年,星期四第三步求精遍歷集合中的所有頂點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中下一個未著色的頂點;}};第十一頁,共三十頁,編輯于2023年,星期四第四步求精引入ADT

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

T(n)第二十二頁,共三十頁,編輯于2023年,星期四2.2.2算法時間復雜性分析方法二:時間復雜性的運算法則對于單個語句,無論是賦值、判斷、加減等,都有T(n)=O(1)。復合結(jié)構(gòu)(多條語句通過控制結(jié)構(gòu)組合)的T(n)分析需應用如下法則:此處設T1(n)=O(f(n)),T2(n)=O(g(n))分別為程序段P1和P2的運行時間。加法規(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))第二十三頁,共三十頁,編輯于2023年,星期四2.2.2算法時間復雜性分析方法三:對三種控制結(jié)構(gòu)進行時間復雜性分析順序結(jié)構(gòu):語句序列s1,…,sk的運行時間由加法原則確定:即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)第二十四頁,共三十頁,編輯于2023年,星期四算法時間復雜性分析實例(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)結(jié)構(gòu)的分析T(n)=O(1)+2(n-1)=O(n)第二十五頁,共三十頁,編輯于2023年,星期四算法時間復雜性分析實例(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)第二十六頁,共三十頁,編輯于2023年,星期四算法時間復雜性分析實例(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的

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論