算法設(shè)計(jì)與分析課件

演算法設(shè)計(jì)與分析

第1章演算法問題求解基礎(chǔ)學(xué)習(xí)要點(diǎn)：理解演算法的概念。理解什麼是程式，程式與演算法的區(qū)別和內(nèi)在聯(lián)繫。章節(jié)內(nèi)容：1.1演算法概述1.3演算法設(shè)計(jì)與分析AnArabianmathematicianAbū’AbudAllāhMuhammadibnMūsāal-Khwārizm(c.780-c.850?)wrotethefamous“Persiantext-book”titledKitābal-jabrwa’l-muqābala”AlgebraAlgorismAlgorithmAlgorithm的由來Arithmetic1.1演算法概述Analgorithmisaprecisedescriptionoftheprocessofsolvingaproblem,consistingoffinitenumberofinstructionswhichcanbeexecutedmechanicallyandproduceadeterministicresult. ——演算法是對某個(gè)問題求解方案的完整而明確的描述，是指令的有限序列。Fiveimportantfeatures:Finiteness——有窮性（演算法必須總能在執(zhí)行有限步之後終止）Definiteness——確定性（組成演算法的每一條指令都是清晰，無歧義的）Input——輸入（演算法有零個(gè)或多個(gè)外部提供的輸入量）Output——輸出（演算法至少產(chǎn)生一個(gè)輸出量）Effectiveness——可行性（演算法的每一條指令必須足夠基本，能夠通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)）“電腦科學(xué)是一門研究演算法的科學(xué)”演算法與程式

程式(Program)是演算法用某種程式設(shè)計(jì)語言的具體實(shí)現(xiàn)。

演算法必須可終止，程式卻沒有這一限制。 即：程式可以不滿足演算法的性質(zhì)(5)—“有窮性”。

例如：

操作系統(tǒng)是一個(gè)在無限迴圈中執(zhí)行的程式，卻不是演算法。因此操作系統(tǒng)是使用電腦語言描述的一個(gè)計(jì)算過程，而不是一個(gè)演算法。演算法描述描述一個(gè)演算法可以用自然語言、流程圖、偽代碼和程式設(shè)計(jì)語言。經(jīng)典演算法舉例

歐幾裏德演算法（輾轉(zhuǎn)相除法）：

求兩整數(shù)m和n的最大公約數(shù)(0≤m<n)

歐幾裏德演算法mnr①輸入m

和n；②求n除以m的餘數(shù)r；③若r等於0，則m為最大公約數(shù)，演算法結(jié)束；否則執(zhí)行第④步；④將m的值放在n中，將r的值放在m中；⑤重新執(zhí)行第②步。自然語言描述：N開始輸入m和n

r=n%mr=0n=m；m=r

輸出m結(jié)束Y流程圖描述：偽代碼描述：1.r=n%m;2.迴圈直到r等於02.1n=m;2.2m=r;2.3r=n%m;3.輸出m;程式設(shè)計(jì)語言描述（遞歸）：intRGcd(intm,intn)//歐幾裏德遞歸演算法{ if(m==0)returnn;//終止條件

returnRGcd(n%m,m);}尾遞歸intGcd(intm,intn){ if(m>n)Swap(m,n); returnRGcd(m,n);}程式1-1歐幾裏德演算法（遞歸）voidSwap(int&a,int&b){ intc=a;a=b;b=c; }程式1-2歐幾裏德演算法（迭代）voidSwap(int&a,int&b){ intc=a;a=b;b=c; }intGcd(intm,intn){ if(m==0)returnn; if(n==0)returnm; if(m>n)Swap(m,n);

while(m>0) {intc=n%m; n=m;m=c; } returnn;}程式設(shè)計(jì)語言描述（迭代）：可見：一個(gè)問題可以設(shè)計(jì)不同的演算法來求解。同一個(gè)演算法可採用不同的形式來表示。程式1-3連續(xù)整數(shù)檢測intGcd(intm,intn){ if(m==0)returnn; if(n==0)returnm; intt=m>n?n:m;

while(m%t||n%t)t--; returnt;}程式設(shè)計(jì)語言描述（連續(xù)整數(shù)檢測）：小思考

若不事先比較m和n的大小，如何實(shí)現(xiàn)歐幾裏德演算法？intGcd(intm,intn){while(m!=0&&n!=0){

if(m>n)m%=n; elsen%=m;}

returnm+n;}程式是否一定會在有限步之內(nèi)終止？小思考

m*n/Gcd(m,n)如何求最小公倍數(shù)？演算法的重要性（AlgorithmEverywhere）ApplicationsHumanGenomeProject:identifying100000genesinhumanDNA,determiningthesequencesofthe3billionchemicalbasepairsthatmakeuphumanDNA,storingthisinformationindatabases,anddevelopingtoolsfordataanalysis.（卡普Karp->華盛頓）Internetservice:e.g.routingthedataElectroniccommerce:public-keycryptographyanddigitalsignaturesSystemsHardwareOperatingsystemsCompilers（克努特Knuth-LR(k)文法）假設(shè)某一負(fù)責(zé)人交給你一個(gè)很難的任務(wù)，幾天後詢問你問題解決了沒有?？赡軙l(fā)生如下圖這樣的情況：問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”答：“我找不到一個(gè)有效的演算法來解決它，沒能完成任務(wù)?！眴枺骸敖唤o你的問題，解決方案設(shè)計(jì)出來了嗎？”答：“我找不到一個(gè)有效的演算法來解決它，因?yàn)檫@樣的演算法是不存在的?！辈贿^，要證明一個(gè)問題不存在有效演算法，往往跟尋找有效演算法一樣難。問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”答：“我找不到一個(gè)有效的演算法來解決它，但不是我不行，因?yàn)樗羞@些名人也都找不到解決它的有效演算法?！盤hilosophyofProblemSolvingTodealwiththosewhichcan’tbesolved,wecompromise；Todealwiththosewhichcanbesolved,wetryourbest；Todistinguishbetweenthetwoclasses,weuseourwit.演算法與圖靈獎(jiǎng)

——超過1/3的Turing獎(jiǎng)獲獎(jiǎng)?wù)咂涑晒c演算法有關(guān)1974-DonaldKnuth(Stanford):“TheArtofComputerProgramming”1976-MichaelRabin(Hebrew)&DanaScott(Oxford):NondeterministicFiniteStateAutomata(NDFSA)1982-StephenCook(Toronto):SatisfiabilityofPropositionCalculusisNP-complete1985-RichardKarp(UCBerkley):Branch-and-BoundMethod1986-JohnHopcroft(Cornell)&RobertTarjan(Princeton):Graphalgorithms1993-JurisHartmanis(Cornell)&RichardStearns(SUNYAlbany):ComputationalComplexityTheory1995-ManualBlum(UCBerkeley):Complexityofrecursivefunctionsanditsapplicationininformationsecurity2000-StephenYau(Princeton):Randomalgorithm,complexityofcommunication2002–RonaldRivest(MIT),AdiShamir(Weizmann),LeonardAdleman(USC):RSAalgorithm

演算法與圖靈獎(jiǎng)

——超過1/3的Turing獎(jiǎng)獲獎(jiǎng)?wù)咂涑晒c演算法有關(guān)有趣的演算法問題背包問題1（物品可分割）：

有一旅行者要從n種物品中選取不超過b公斤重的行李隨身攜帶，要求總價(jià)值最大。 例：設(shè)背包的容量為50千克。物品1重10千克，價(jià)值60元；物品2重20千克，價(jià)值100元；物品3重30千克，價(jià)值120元。求總價(jià)值最大。背包問題2（物品不可分割）：

設(shè)有n=8個(gè)體積分別為54，45，43，29，23，21，14，1的物體和一個(gè)容積為C=110的背包，問選擇哪幾個(gè)物體裝入背包可以使其裝的最滿。有趣的演算法問題約瑟夫環(huán)（Josephuscycle）

編號為1，2，3，……，n的n個(gè)人按順時(shí)針方向圍坐一圈。任選一個(gè)正整數(shù)作為報(bào)數(shù)上限m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出列。從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到最後圈中只剩下最後一個(gè)人（勝利者）。請?jiān)O(shè)計(jì)程式輸出勝利者。

①一般解法：用鏈表實(shí)現(xiàn)②數(shù)學(xué)解法：voidmain(){

intn,m,i,s=0;

scanf("%d%d",&n,&m);

for(i=2;i<=n;i++)s=(s+m)%i;

printf("Thewinneris%d\n",s+1);

}有趣的演算法問題皇后問題（回溯法經(jīng)典問題）

這是高斯1850年提出的一個(gè)著名問題：國際象棋中的“皇后”在橫向、直向、和斜向都能走步和吃子，問在n×n格的棋盤上如何能擺上n個(gè)皇后而使她們都不能互相吃。

當(dāng)n很大時(shí)，問題很難。 對於n=8,現(xiàn)已知此問題共有92種解，但只有12種是獨(dú)立的，其餘的都可以由這12種利用對稱性或旋轉(zhuǎn)而得到。 設(shè)n=4，試一試？有趣的演算法問題平面圖的四色猜想問題（近代三大數(shù)學(xué)難題之一,與費(fèi)馬定理、哥德巴赫猜想並稱近代數(shù)學(xué)三大難題。

）

在1852年，由畢業(yè)於倫敦大學(xué)的弗南西斯-古德裏（FrancisGuthrie)進(jìn)行地圖著色時(shí)提出:一個(gè)平面圖是否用四種顏色就可使相鄰的區(qū)域顏色都不相同？——這是第一個(gè)主要由電腦證明的理論。（1976年，KennethAppel與WolfgangHaken，美國伊利諾斯大學(xué)，兩臺電腦1200小時(shí)、100億次判斷。）有趣的演算法問題旅行售貨員問題（最小哈密頓回路）

設(shè)有n個(gè)城市，已知任意兩城市間距離，現(xiàn)有一推銷員想從某一城市出發(fā)巡迴經(jīng)過每一城市（且每城市只經(jīng)過一次），最後又回到出發(fā)點(diǎn)，問如何找一條最短路徑。設(shè)距離矩陣如下：試一試求出最短路徑。Algorithmvs.ComputerScience

Thestudyofalgorithmsismorethanabranchofcomputerscience.Itiscentraltoallareasofcomputerscience,and,inallfairness,canbesaidtoberelevanttomostofscience,businessandtechnology,particularlyapplicabletothosedisciplinesthatbenefitfromtheuseofcomputers,andthesearefastbecominganoverwhelmingmajority.Sometimespeopleask:“Whatreallyiscomputerscience?Whydon’twehavetelephonescience?Telephone,itmightbeargued,areasimportanttomodernlifeascomputerare,perhapsevenmoreso.Aslightlymorefocusedquestioniswhethercomputerscienceisnotcoveredbysuchclassicaldisciplinesasmathematics,physics,electricalengineering,linguistics,logicandphilosophy.Wewoulddobestnottopretendthatwecananswerthesequestionshereandnow.Thehope,however,isthatthecoursewillimplicitlyconveysomethingoftheuniquenessanduniversalityofthestudyofalgorithm,andhencesomethingoftheimportanceofcomputerscienceasanautonomousfieldofstudy.

-“Algorithmics,theSpiritofComputing”1.3演算法設(shè)計(jì)與分析如何設(shè)計(jì)演算法——選擇演算法設(shè)計(jì)策略 所求問題符合某種演算法設(shè)計(jì)策略處理的問題特性。如何表示演算法——描述演算法 自然語言、流程圖、偽代碼、程式設(shè)計(jì)語言。本書中使用C/C++語言描述。如何確認(rèn)演算法——正確性證明 對於所有合法的輸入，能在有限時(shí)間內(nèi)輸出正確的結(jié)果，稱演算法是正確的。確認(rèn)一個(gè)演算法是否正確的活動，稱為演算法確認(rèn)；（大多數(shù)情況下，人們通過程式測試和調(diào)試來排錯(cuò)進(jìn)行演算法的正確性證明）使用數(shù)學(xué)方法證明演算法的正確性，稱為演算法證明；（常用的演算法正確性證明方法為數(shù)學(xué)歸納法。如：P9證明程式1-1的正確性）如何分析演算法演算法分析指對演算法的執(zhí)行時(shí)間和所需空間的估算。設(shè)計(jì)出複雜性盡可能低的演算法，或?qū)ΜF(xiàn)有的演算法進(jìn)行改進(jìn)；（設(shè)計(jì)演算法）從解決同一問題的多種演算法中選出複雜性最低者。（選擇演算法）程式1-1歐幾裏德演算法（遞歸）voidSwap(int&a,int&b){ intc=a;a=b;b=c; }intGcd(intm,intn){ if(m>n)Swap(m,n); returnRGcd(m,n);}intRGcd(intm,intn)//歐幾裏德遞歸演算法{ if(m==0)returnn;//終止條件

returnRGcd(n%m,m);}1.3演算法設(shè)計(jì)與分析如何設(shè)計(jì)演算法——選擇演算法設(shè)計(jì)策略 所求問題符合某種演算法設(shè)計(jì)策略處理的問題特性。如何表示演算法——描述演算法 自然語言、流程圖、偽代碼、程式設(shè)計(jì)語言。本書中使用C/C++語言描述。如何確認(rèn)演算法——正確性證明 對於所有合法的輸入，能在有限時(shí)間內(nèi)輸出正確的結(jié)果，稱演算法是正確的。確認(rèn)一個(gè)演算法是否正確的活動，稱為演算法確認(rèn)；（大多數(shù)情況下，人們通過程式測試和調(diào)試來排錯(cuò)進(jìn)行演算法的正確性證明）使用數(shù)學(xué)方法證明演算法的正確性，稱為演算法證明；（常用的演算法正確性證明方法為數(shù)學(xué)歸納法。如：P9證明程式1-1的正確性）如何分析演算法演算法分析指對演算法的執(zhí)行時(shí)間和所需空間的估算。設(shè)計(jì)出複雜性盡可能低的演算法，或?qū)ΜF(xiàn)有的演算法進(jìn)行改進(jìn)；（設(shè)計(jì)演算法）從解決同一問題的多種演算法中選出複雜性最低者。（選擇演算法）那麼，如何證明演算法是不正確的？演算法問題的求解過程(ProblemSolving)理解問題選擇演算法設(shè)計(jì)策略（確定數(shù)據(jù)結(jié)構(gòu)）設(shè)計(jì)演算法正確性證明分析演算法編寫程式代碼補(bǔ)充：數(shù)學(xué)歸納法（例1）證明：平面上任意條直線構(gòu)成的區(qū)域可以僅使用兩種顏色進(jìn)行著色。證明：顯然，直線數(shù)目n=1時(shí)可以僅需兩種顏色進(jìn)行著色。假設(shè)平面上小於n條直線構(gòu)成的區(qū)域能僅用兩種顏色來著色。那麼考慮n條直線時(shí)的情況，在添加第n條直線後如何對原著色方案進(jìn)行修改：根據(jù)區(qū)域位於第n條直線的哪一側(cè)，可以把這些區(qū)域分成兩組，保留其中一組區(qū)域的顏色，反轉(zhuǎn)另一組區(qū)域的顏色。如何證明該方案為有效著色？補(bǔ)充：數(shù)學(xué)歸納法（例1）證明：平面上任意條直線構(gòu)成的區(qū)域可以僅使用兩種顏色進(jìn)行著色?，F(xiàn)證該方案為有效著色：考察兩個(gè)相鄰區(qū)域R1和R2。如果這兩個(gè)區(qū)域都在第n條直線的同側(cè)，那麼根據(jù)歸納假設(shè)，它們在添上第n條直線之前顏色就不同。雖然它們可能需要改變著色，但無論如何它們的顏色仍然是不同的。如果這兩個(gè)區(qū)域的公共邊是第n條直線的一部分，那麼在添上第n條直線前它們屬於同一區(qū)域。既然反轉(zhuǎn)了其中一個(gè)區(qū)域的顏色，那麼現(xiàn)在它們的顏色一定不同。補(bǔ)充：數(shù)學(xué)歸納法（例2）證明下麵猜想：下麵三角形中第i行的和是i3。11=538=+971127=++1315191764=+++2927252123125=++++思路：要證明第i行的和是i3，只需證明第(i+1)行和第i行的差是(i+1)3-i3。補(bǔ)充：數(shù)學(xué)歸納法（例2）11=538=+971127=++1315191764=+++2927252123125=++++證明：由於這些數(shù)都是按序排列的奇數(shù)，且第i行有i個(gè)數(shù)。所以第(i+1)行第1個(gè)數(shù)和第i行第1個(gè)數(shù)相差2i。同樣，第2個(gè)數(shù)，第3個(gè)數(shù)，第4個(gè)數(shù)均是這樣......一共有i個(gè)差，每個(gè)差2i。另外，第(i+1)行末尾的最後一個(gè)數(shù)，不與上一行的任何一個(gè)數(shù)相匹配。因此，這兩行的差就是2i2加上第(i+1)行的最後一個(gè)數(shù)。因此僅需證明第(i+1)行的最後一個(gè)數(shù)值為(i+1)3-i3-2i2=i2+3i+1導(dǎo)出命題（將一個(gè)求和的問題規(guī)約成了求某一項(xiàng)的問題）補(bǔ)充：數(shù)學(xué)歸納法（例2）11=538=+971127=++1315191764=+++2927252123125=++++證明：上述命題對i=1時(shí)成立。則只要證明第（i+1）行的最後一個(gè)數(shù)和第i行的最後一個(gè)數(shù)之差等於[i2+3i+1]-[(i-1)2+3(i-1)+1]=2i+2即可。而我們已經(jīng)得到第(i+1)行和第i行的對應(yīng)項(xiàng)的差是2i。因此第(i+1)行最後一個(gè)數(shù)與第i行的最後一個(gè)數(shù)的差是2i+2，猜測成立，證明完成。證明嵌套的歸納假設(shè)：第（i+1）行的最後一個(gè)數(shù)是i2+3i+1。補(bǔ)充：數(shù)學(xué)歸納法（例3）證明（歐拉公式）：任意一張連通平面圖的節(jié)點(diǎn)數(shù)(V)、邊數(shù)(E)和麵數(shù)(F)的關(guān)係可由公式V+F=E+2表示。又如：上圖包含11個(gè)節(jié)點(diǎn)、19條邊和10個(gè)面。如：正方形包含4個(gè)節(jié)點(diǎn)、4條邊和2個(gè)面。補(bǔ)充：數(shù)學(xué)歸納法（例3）證明（歐拉公式）：任意一張連通平面圖的節(jié)點(diǎn)數(shù)(V)、邊數(shù)(E)和麵數(shù)(F)的關(guān)係可由公式V+F=E+2表示。證明：■首先考察只有一個(gè)面的圖。這樣的圖不包含回路，否則，回路至少構(gòu)成一個(gè)面，回路以外構(gòu)成另一個(gè)面。這種連通無回路的圖被稱為樹，現(xiàn)證明對任意樹V+1=E+2成立：（也即只需證明：有V個(gè)頂點(diǎn)的樹有V-1條邊即可。）證明：顯然，有1個(gè)頂點(diǎn)的樹有0條邊。假設(shè)有n個(gè)頂點(diǎn)的樹有n-1條邊成立，則考察有n+1個(gè)節(jié)點(diǎn)的樹：至少存在一個(gè)節(jié)點(diǎn)，與樹中其他節(jié)點(diǎn)間只有一條邊相連。（否則若所有節(jié)點(diǎn)都與至少2條邊相連，則一定會有回路存在，與樹的定義矛盾。）將該節(jié)點(diǎn)連同與之相連的一條邊從樹上移走，得到的圖仍是一棵樹（只不過少了一個(gè)節(jié)點(diǎn)和一條邊）。根據(jù)歸納假設(shè)條件此時(shí)滿足V+1=E+2?？芍猲+1個(gè)節(jié)點(diǎn)時(shí)，命題也成立，得證。補(bǔ)充：數(shù)學(xué)歸納法（例3）證明（歐拉公式）：任意一張連通平面圖的節(jié)點(diǎn)數(shù)(V)、邊數(shù)(E)和麵數(shù)(F)的關(guān)係可由公式V+F=E+2表示。只有一個(gè)面的圖滿足V+1=E+2已證，歸納基礎(chǔ)成立。假設(shè)有n個(gè)面的平面圖如果有E條邊和V個(gè)節(jié)點(diǎn)，那麼V+n=E+2?？疾煊衝+1個(gè)面的圖：一定存在某個(gè)面f，使得f與最外面的那個(gè)面相鄰。因?yàn)閒是面，所以f一定由回路圍成。那麼我們就去掉f與最外面的那個(gè)面之間的那條邊，這樣就少了一個(gè)面和一條邊。根據(jù)歸納假設(shè)條件，此時(shí)滿足V+n=E+2。可知n+1個(gè)面時(shí)，命題也成立，得證。證明過程中對其中一個(gè)參數(shù)（面數(shù)F）進(jìn)行歸納，而歸納基礎(chǔ)的成立又需要對另一個(gè)參數(shù)（結(jié)點(diǎn)數(shù)V）進(jìn)行歸納。說明：選擇歸納順序需謹(jǐn)慎，對演算法的效率有很大影響。常見演算法種類精確演算法——總能保證求得問題的精確解。啟發(fā)式演算法——通過使用某種規(guī)則、簡化或智能猜測來減少問題求解時(shí)間。如：局部擇優(yōu)搜索法、最好優(yōu)先搜索法等?！荒鼙ＷC求得的解必定是問題的最優(yōu)解，甚至不一定是問題的可行解，但常常能在合理的時(shí)間內(nèi)得到令人滿意的結(jié)果近似演算法——解最優(yōu)化問題時(shí)最後得到的結(jié)果能保證在一定的誤差之內(nèi)（近似解，而不是最優(yōu)解）的演算法。概率（隨機(jī)）演算法——帶有隨機(jī)操作的一類演算法。在演算法計(jì)算的某一步或某些步產(chǎn)生符合規(guī)定要求的亂數(shù)，然後演算法的執(zhí)行根據(jù)產(chǎn)生的亂數(shù)選擇下一個(gè)計(jì)算步驟?！Y(jié)果可能不確定——大致分為四類：數(shù)值概率演算法（近似解，數(shù)值問題求解）、MonteCarle演算法（確定解，但不一定正確）、LasVegas演算法（正確解，但可能找不到）、Sherwood演算法（總能得到一個(gè)正確解。當(dāng)確定演算法最壞情況下的複雜性與平均情況下有較大差別時(shí)，可引入隨機(jī)性改造為舍伍德演算法。）/algorithm/?SchoolofComputerScienceandTechnology,SWUST41重要的問題類型排序(Sorting)查找(Search)串處理(String)圖問題(Graph)組合問題(Combination)幾何問題(Geometry)數(shù)值問題/algorithm/?SchoolofComputerScienceandTechnology,SWUST42基本數(shù)據(jù)結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)數(shù)組，串，單（雙）鏈表，棧，佇列圖有向圖，無向圖，加權(quán)圖樹自由樹，有根樹有序樹集合與字典2.1演算法複雜度

好演算法的4個(gè)重要特徵：Correctness——正確性注意區(qū)分“正確性”和“健壯性”的概念：演算法正確性——在合法的輸入下，演算法應(yīng)實(shí)現(xiàn)預(yù)先規(guī)定的功能和計(jì)算精度要求。程式健壯性——當(dāng)輸入不合法的數(shù)據(jù)時(shí)，程式應(yīng)能做適當(dāng)處理而不至於引起嚴(yán)重後果。正確性和健壯性互相補(bǔ)充。程式可靠性——在正常情況下能正確地工作，在異常情況下也能做出適當(dāng)處理。2.1演算法複雜度

好演算法的4個(gè)重要特徵：Correctness——正確性Simplicity,clarity——簡明性遺憾的是，簡單的演算法不一定高效思路清晰、層次分明、容易理解、利於編碼和調(diào)試。2.1演算法複雜度

好演算法的4個(gè)重要特徵：Correctness——正確性Simplicity,clarity——簡明性Amountoftime/spaceused——效率執(zhí)行演算法所需的時(shí)間和存儲空間演算法設(shè)計(jì)者常常需要在演算法的簡明性和效率之間作出謹(jǐn)慎的選擇2.1演算法複雜度

好演算法的4個(gè)重要特徵：Correctness——正確性Simplicity,clarity——簡明性Amountoftime/spaceused——效率Optimality——最優(yōu)性演算法執(zhí)行時(shí)間達(dá)到求解該類問題所需時(shí)間的下界。與所求解問題自身的複雜程度有關(guān)。ForproblemP,thealgorithmAdoesatmostWA(n)stepsintheworstcase(upperbound)F

isalowerboundforaclassofalgorithm.

(lowerbound)

IfWA=F,then

Aisoptimal.Definitionoftheoptimalalgorithm（最優(yōu)演算法）meansthat:Foranyalgorithmintheclass,andanyinputofsizen,thereissomeinputofsizenforwhichthealgorithmmustperformatleastF(n)basicoperations.又如：可證排序問題的時(shí)間複雜度下界為

(nlogn)。則最壞時(shí)間複雜性為O(nlogn)的排序演算法是最優(yōu)演算法。因此：堆排序演算法和兩路合併排序演算法都是最優(yōu)演算法。例如:FindMax(intL[])//求n個(gè)元素中的最大元素{ intmax=L[0];inti=1; while(i<n) { if(max<L[i])max=L[i]; i=i+1; }}最優(yōu)演算法影響程式運(yùn)行時(shí)間的因素程式所依賴的演算法問題規(guī)模和輸入數(shù)據(jù)電腦系統(tǒng)性能根本的、起決定作用的數(shù)值大小和狀態(tài)硬體系統(tǒng)性能（CPU速度）和軟體系統(tǒng)性能（操作系統(tǒng)、編譯器）輸入、輸出——運(yùn)行一個(gè)演算法所需的時(shí)間和空間資源的量。演算法的時(shí)間複雜性（TimeComplexity）——T(n)演算法的空間複雜性（SpaceComplexity）——S(n)

其中n是問題的規(guī)模（輸入大?。┭菟惴ㄑ}雜度HowtoMeasure?

MachineindependentLanguageindependentProgrammingstyleindependentImplementationindependent演算法的時(shí)間複雜度演算法的時(shí)間複雜度——演算法運(yùn)行所需的時(shí)間最好、最壞和平均時(shí)間複雜度(不考慮電腦因素對演算法分析的影響）最好情況（出現(xiàn)概率較大時(shí)分析）最差情況（即時(shí)系統(tǒng)）平均情況（已知輸入數(shù)據(jù)是如何分佈的，通常假設(shè)等概率分佈）演算法的時(shí)間複雜度（1）最好情況下的時(shí)間複雜性：

B(n)=Tmin(n)=min{T(n,I)|I∈Dn

}（2）最壞情況下的時(shí)間複雜性：

W(n)=Tmax(n)=max{T(n,I)|I∈Dn

} （3）平均情況下的時(shí)間複雜性：

A(n)=Tavg(n)

= I:問題規(guī)模為n的實(shí)例。Dn:規(guī)模為n的所有合法輸入的集合。p(I):實(shí)例I出現(xiàn)的概率。演算法的空間複雜度演算法的空間複雜度

——演算法運(yùn)行所需的存儲空間固定空間需求 與所處理數(shù)據(jù)的大小和個(gè)數(shù)無關(guān)，即與問題實(shí)例的特徵無關(guān)。（包括：程式代碼、常量、簡單變數(shù)、定長成分的結(jié)構(gòu)變數(shù)所占的空間）可變空間需求 與演算法執(zhí)行過程中處理的特定數(shù)據(jù)的規(guī)模有關(guān)。（如：數(shù)據(jù)元素所占的空間，演算法執(zhí)行所需的額外空間—如遞歸演算法所需系統(tǒng)?？臻g）通過程式步來分析演算法的時(shí)間複雜度求數(shù)組元素累加之和的迭代程式：(P20程式2-1)floatSum(floatlist[],constintn){ floattempsum=0.0; //1for(inti=0;i<n;i++) //n+1{tempsum+=list[i]; //n}returntempsum; //1}程式總步數(shù)為：2n+3求數(shù)組元素累加之和的遞歸程式：(P21程式2-2)floatRSum(floatlist[],constintn){if(n) //1{

return

RSum(list,n-1)+list[n-1]; //1}

return0; //1}程式總步數(shù)為：2n+2但遞歸調(diào)用引起的迴圈計(jì)算和使用for語句的迴圈計(jì)算所需的開銷是不同的。遞歸需要耗費(fèi)更多的時(shí)間和空間資源。可見：程式步數(shù)並不能確切反映程式運(yùn)行的實(shí)際時(shí)間。2.2漸近表示法程式步的精確計(jì)算是困難的，且程式步並不能確切反映程式運(yùn)行的實(shí)際時(shí)間。因此引入漸近時(shí)間複雜度,使用程式步在數(shù)量級上估計(jì)一個(gè)演算法的執(zhí)行時(shí)間，從而實(shí)現(xiàn)演算法的事前分析。在數(shù)學(xué)上，演算法的漸近複雜度t(n)是T(n)的漸近運(yùn)算式，是T(n)略去低階項(xiàng)留下的主項(xiàng)，它比T(n)簡單。 例如:T(n)=3n2+4nlogn+7與t(n)=3n2

當(dāng)n→∞時(shí)，有(T(n)-t(n))/T(n)→0。

那麼在演算法分析中呢？漸近分析的記號：O、Ω、θ、o、ω

在下面的討論中，對所有n，f(n)≥0，g(n)≥0。（1）漸近上界記號O

如果存在正常數(shù)c和自然數(shù)n0，使得當(dāng)n

n0時(shí)有f(n)≤cg(n)，則稱函數(shù)f(n)當(dāng)n充分大時(shí)有上界，且g(n)是它的一個(gè)上界，記做f(n)=O(g(n))

。即f(n)的階不高於g(n)的階。

上界記號O舉例：C0=O(1) f(n)=C0為非零常數(shù)，取c=c0100n+6=O(n) 取c=101,n0=66*2n+n2=O(n2) 取c=7,n0=43logn+2*n+n2=O(n2) 取c=6,n0=1O(1)表示常數(shù)計(jì)算時(shí)間，代表演算法只需執(zhí)行有限個(gè)程式步。如何證明？證明見P22

（定理2-1）如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多項(xiàng)式，且am>0，則f(n)=O(nm)。例如：程式2-1floatSum(floatlist[],constintn){ floattempsum=0.0; //1for(inti=0;i<n;i++) //n+1{tempsum+=list[i];

//n}returntempsum; //1}可以通過考察一個(gè)程式中關(guān)鍵操作（keyoperation）的執(zhí)行次數(shù)，來估算演算法的漸近時(shí)間複雜度。關(guān)鍵操作！執(zhí)行次數(shù)n和總的程式步2n+3有相同的漸近時(shí)間複雜度O(n)。關(guān)鍵操作通常是位於演算法最內(nèi)層迴圈的程式步（或語句），是演算法中執(zhí)行次數(shù)最多的操作（程式步）?？梢酝ㄟ^考察一個(gè)程式中關(guān)鍵操作（keyoperation）的執(zhí)行次數(shù)，來估算演算法的漸近時(shí)間複雜度。關(guān)鍵操作通常是位於演算法最內(nèi)層迴圈的程式步（或語句），是演算法中執(zhí)行次數(shù)最多的操作（程式步）。例如：程式2-3矩陣乘法for(i=0;i<n;i++) //n+1for(j=0;j<n;j++) //n(n+1){ c[i][j]=0; //n2 for(k=0;k<n;k++) //n2(n+1)

c[i][j]+=a[i][k]*b[k][j];

//n3}關(guān)鍵操作！執(zhí)行次數(shù)n3和總的程式步2n3+3n2+2n+1有相同的漸近時(shí)間複雜度O(n3)?？梢酝ㄟ^考察一個(gè)程式中關(guān)鍵操作（keyoperation）的執(zhí)行次數(shù)，來估算演算法的漸近時(shí)間複雜度。關(guān)鍵操作通常是位於演算法最內(nèi)層迴圈的程式步（或語句），是演算法中執(zhí)行次數(shù)最多的操作（程式步）。例如：程式1-2歐幾裏德迭代演算法intGcd(intm,intn){ if(m==0)returnn; if(n==0)returnm; if(m>n)Swap(m,n);

while(m>0)

{intc=n%m; n=m;m=c; } returnn;}有時(shí)候演算法時(shí)間的計(jì)算並非直截了當(dāng)，while迴圈每次迭代後餘數(shù)值並非按常數(shù)因數(shù)遞減。如何計(jì)算迭代次數(shù)？定理2-2如果n>m，則nmodm<n/2。每次迭代的餘數(shù)最多是原始值的一半，因此迭代次數(shù)為O(logn)。歐幾裏德演算法的時(shí)間複雜度為O(logn+logm)。（2）漸近下界記號

如果存在正常數(shù)c和自然數(shù)n0，使得當(dāng)n

n0時(shí)有f(n)≥cg(n)，則稱函數(shù)f(n)當(dāng)n充分大時(shí)有下界，且g(n)是它的一個(gè)下界，記做f(n)=

(g(n))

。即f(n)的階不低於g(n)的階。

f(n)=O(g(n))

g(n)=

(f(n))證明（略）（定理2-3）如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多項(xiàng)式，且am>0，則f(n)=Ω(nm)。（3）緊漸近界記號

如果存在正常數(shù)c1,c2和n0，使得當(dāng)n

n0時(shí)有c1g(n)≤f(n)≤

c2g(n)，則稱函數(shù)f(n)與函數(shù)g(n)同階，記做f(n)＝

(g(n))。即f(n)與g(n)的增長階數(shù)相同。

(g(n))=O(g(n))

(g(n))即：f(n)=

(g(n))當(dāng)且僅當(dāng)f(n)=O(g(n))且f(n)=(g(n))證明（略）

（定理2-4）如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多項(xiàng)式，且am>0，則f(n)=Θ(nm)。（4）非緊上界記號o

如果對於任何正常數(shù)c>0都存在正整數(shù)n0>0，使得當(dāng)n

n0時(shí)有f(n)＜cg(n)（等價(jià)於:n

時(shí)，f(n)/g(n)0），則稱函數(shù)f(n)當(dāng)n充分大時(shí)的階比g(n)低，記做f(n)=o(g(n))。（5）非緊下界記號

如果對於任何正常數(shù)c>0都存在正整數(shù)n0>0，使得當(dāng)n

n0時(shí)有f(n)＞cg(n)（等價(jià)於n

時(shí)，f(n)/g(n)

），則稱函數(shù)f(n)當(dāng)n充分大時(shí)的階比g(n)高，記做f(n)＝

(g(n))。f(n)=o(g(n))

g(n)=

(f(n))

漸近分析中函數(shù)比較f(n)=O(g(n))

f(n)g(n);f(n)=

(g(n))

f(n)g(n);f(n)=

(g(n))

f(n)=g(n);f(n)=o(g(n))

f(n)<g(n);f(n)=

(g(n))

f(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，有g(shù)1(n)

c2g(n)。

令c3=max{c1,c2}，n3=max{n1,n2}， 則對所有的n

n3，有

f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n) =c3(f(n)+g(n))

2c3max{f(n),g(n)} =O(max{f(n),g(n)})思考題：證明O(f(n))+O(g(n))=O(max{f(n),g(n)})

順序搜索演算法template<classType>intseqSearch(Type*a,intn,Typek){for(inti=0;i<n;i++) if(a[i]==k)returni;return-1;}時(shí)間複雜度綜合分析（例1）（1）最壞情況下：Tmax(n)=max{T(I)|size(I)=n}=O(n)（2）最好情況下：Tmin(n)=min{T(I)|size(I)=n}=O(1)（3）平均情況下，假設(shè)：搜索成功的概率為p(0

p

1)；在數(shù)組的每個(gè)位置i(0

i<n)搜索成功的概率相同，均為p/n。

非遞歸演算法的時(shí)間複雜度分析法則：（1）for/while迴圈 循環(huán)體內(nèi)計(jì)算時(shí)間*迴圈次數(shù)；（2）嵌套迴圈 循環(huán)體內(nèi)計(jì)算時(shí)間*所有迴圈次數(shù)；（3）順序語句 各語句計(jì)算時(shí)間相加；（4）if-else語句

if語句計(jì)算時(shí)間和else語句計(jì)算時(shí)間的較大者。template<classType>voidinsertion_sort(Type*a,intn){Typekey;//cost timesfor(inti=1;i<n;i++){//c1 n

key=a[i];//c2 n-1

intj=i-1;//c3 n-1

while(j>=0&&a[j]>key){//c4 sumofti a[j+1]=a[j];//c5 sumof(ti-1)

j--;//c6 sumof(ti-1) }a[j+1]=key;//c7 n-1

}}時(shí)間複雜度綜合分析（例2）在最好情況下，ti=1,for1

i<n;在最壞情況下，ti＝i+1,for1

i<n;對於輸入數(shù)據(jù)a[i]=n-i,i=0,1,…,n-1，演算法insertion_sort達(dá)到其最壞情形。while首句：while循環(huán)體：演算法按時(shí)間複雜度分類多項(xiàng)式時(shí)間演算法——漸近時(shí)間複雜度有多項(xiàng)式時(shí)間限界的演算法O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時(shí)間演算法——漸近時(shí)間複雜度為指數(shù)函數(shù)限界的演算法O(2n)<O(n!)<O(nn)（參見表2-1）演算法分析中常見的時(shí)間複雜度函數(shù)SortinganArrayof1MillionNumbersComputerA1000MipsComputerB10MipsUsinginsertionsort,takingtime2n2:2000seconds!Usingmergesort,takingtime50nlogn:100seconds!小規(guī)模數(shù)據(jù)（參見圖2-1）中等規(guī)模數(shù)據(jù)

補(bǔ)充：C/C++知識點(diǎn)復(fù)習(xí)用c++描述演算法（1）選擇語句：1.1if語句：1.2？語句：

if(expression)statement;elsestatement;exp1?exp2:exp3y=x>9?100:200;等價(jià)於：

if(x>9)y=100;elsey=200;1.3switch語句：switch(expression){case1:statementsequence;break;case2:statementsequence;break;

default:statementsequence;}（2）迭代語句：2.1for迴圈：

for(init;condition;inc)statement;2.2while迴圈：

while(condition)statement;2.3do-while迴圈：

do{ statement; }while(condition);（3）跳轉(zhuǎn)語句：3.1return語句：

returnexpression;3.2goto語句：

gotolabel;

label:（4）函數(shù)：例：

return-typefunctionname(para-list){bodyofthefunction}intmax(intx,inty){returnx>y?x:y;}（5）範(fàn)本template

：template<classType>Typemax(Typex,Typey){returnx>y?x:y;}inti=max(1,2)；doublex=max(1.0,2.0)；（6）動態(tài)存儲分配：6.1運(yùn)算符new：

運(yùn)算符new用於動態(tài)存儲分配，返回一個(gè)指向所分配空間的指針。 例：int

y；y=newint；

y=10； 也可將上述各語句作適當(dāng)合併如下：

int

y=newint；

y=10； 或 int

y=newint(10)； 或 int

y；y=newint(10)；

為了在運(yùn)行時(shí)創(chuàng)建一個(gè)大小可動態(tài)變化的一維浮點(diǎn)數(shù)組x，可先將x聲明為一個(gè)float類型的指針。然後用new為數(shù)組動態(tài)地分配存儲空間。例：float

p=newfloat[n]； 創(chuàng)建一個(gè)大小為n的一維浮點(diǎn)數(shù)組。運(yùn)算符new分配n個(gè)浮點(diǎn)數(shù)所需的空間，並返回指向第一個(gè)浮點(diǎn)數(shù)的指針。 然後可用p[0]，p[1]，…，p[n-1]來訪問每個(gè)數(shù)組元素。6.2一維數(shù)組：例：

intn=5; int*p=newint[n]; for(inti=0;i<n;i++) { p[i]=i; cout<<p[i]; }

當(dāng)動態(tài)分配的存儲空間已不再需要時(shí)應(yīng)及時(shí)釋放所佔(zhàn)用的空間。用運(yùn)算符delete來釋放由new分配的空間。 例：deletey；

delete[]x； 分別釋放分配給

y的空間和分配給一維數(shù)組x的空間。6.3運(yùn)算符delete：創(chuàng)建類型為Type的動態(tài)工作數(shù)組，這個(gè)數(shù)組有rows行和cols列。template<classType>voidMake2DArray(Type**&x,introws,intcols){x=newType*[rows];for(inti=0;i<rows;i++)x[i]=newType[cols];}6.4動態(tài)二維數(shù)組：當(dāng)不再需要一個(gè)動態(tài)分配的二維數(shù)組時(shí)，可按以下步驟釋放它所佔(zhàn)用的空間。首先釋放在for迴圈中為每一行所分配的空間。然後釋放為行指針分配的空間。template<classType>void

Delete2DArray(Type**&x,introws){for(inti=0;i<rows;i++) delete[]x[i];delete[]x;x=0;}釋放空間後將x置為0，以防繼續(xù)訪問已被釋放的空間。作業(yè)：

P332-8(僅需給出劃線語句執(zhí)行次數(shù)和漸近時(shí)間複雜度）

2-10 2-13(更正）關(guān)鍵：根據(jù)遞歸過程建立遞推關(guān)係式，然後求解這個(gè)遞推關(guān)係式。猜測技術(shù):

對遞推關(guān)係式估計(jì)一個(gè)上限，然後（用數(shù)學(xué)歸納法）證明它正確。附錄：遞歸演算法2.擴(kuò)展遞歸技術(shù)

?íì>+==15)2(217)(2nnnTnnT222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+×′+++=+++=++=+=--L)(2nO==。。。3.通用分治遞推式大小為n的原問題分成若干個(gè)大小為n/b的子問題，其中a個(gè)子問題需要求解，而cnk是合併各個(gè)子問題的解需要的工作量。

?íì>+==1)(1)(ncnbnaTncnTk???íì<=>=kkkbkkabanObannObanOnTb)()log()()(log附錄：漸近分析記號的若干性質(zhì)（1）傳遞性：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)=

(h(n))

f(n)=

(h(n))；（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(n))

g(n)=

(f(n))；f(n)=o(g(n))

g(n)=

(f(n))；（5）算術(shù)運(yùn)算：O(f(n))+O(g(n))=

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))；其中c是一個(gè)正的常數(shù)；如果g(n)=O(f(n))

則O(f(n))+O(g(n))=

O(f(n))。f=O(f)。取整函數(shù)

x

：不大於x的最大整數(shù)；

x

：不小於x的最小整數(shù)。

x-1<x

x

x<x+1；

n/2

+n/2=n;附錄：演算法漸近複雜性分析中常用函數(shù)指數(shù)函數(shù)（

對於正整數(shù)m,n和實(shí)數(shù)a>0）

(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1

an為單調(diào)遞增函數(shù);

a>1

nb=o(an)

對數(shù)函數(shù)

logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)k;loglogn=log(logn);

|x|1forx>-1,foranya>0, logn=o(na)階乘函數(shù)

107演算法的經(jīng)驗(yàn)分析對演算法效率做經(jīng)驗(yàn)分析的通用方案瞭解試驗(yàn)的目的決定用來度量效率的量度M和度量單位（單位時(shí)間內(nèi)的操作次數(shù)）決定輸入樣本的特性為實(shí)驗(yàn)準(zhǔn)備演算法的程式實(shí)現(xiàn)生成輸入樣本對輸入樣本進(jìn)行計(jì)算，並記錄觀察到的實(shí)驗(yàn)數(shù)據(jù)分析獲得的實(shí)驗(yàn)數(shù)據(jù)108109演算法可視法通過使用圖形來傳達(dá)關(guān)於演算法的一些有用資訊。演算法可視法的種類：靜態(tài)演算法可視法動態(tài)演算法可視法(演算法動畫,AlgorithmAnimation)110靜態(tài)演算法可視法111靜態(tài)演算法可視法5.1分治法的一般方法分治法——將一個(gè)複雜的問題分解成若干個(gè)規(guī)模較小、相互獨(dú)立，但類型相同的子問題求解；然後再將各子問題的解組合成原始問題的一個(gè)完整答案，這樣的問題求解策略就叫分治法。將要求解的較大規(guī)模的問題分割成k個(gè)更小規(guī)模的子問題。分治演算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=對這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。對這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)將求出的小規(guī)模的問題的解合併為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)將求出的小規(guī)模的問題的解合併為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)分治法的設(shè)計(jì)思想是:將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。分治法的適用條件

分治法所能解決的問題一般具有以下幾個(gè)特徵：該問題的規(guī)模縮小到一定的程度就可以容易地解決；因?yàn)閱栴}的計(jì)算複雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個(gè)特徵。分治法的適用條件

分治法所能解決的問題一般具有以下幾個(gè)特徵：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題；這條特徵是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特徵反映了遞歸思想的應(yīng)用。分治法的適用條件

分治法所能解決的問題一般具有以下幾個(gè)特徵：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題；利用該問題分解出的子問題的解可以合併為該問題的解；能否利用分治法完全取決於問題是否具有這條特徵。如果具備了前兩條特徵，而不具備這一特徵，則可以考慮貪心法或動態(tài)規(guī)劃法。分治法的適用條件

分治法所能解決的問題一般具有以下幾個(gè)特徵：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題；利用該問題分解出的子問題的解可以合併為該問題的解；該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。這條特徵涉及到分治法的效率。如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重複地解公共的子問題，此時(shí)雖然也可用分治法，但一般用動態(tài)規(guī)劃法較好。分治法求解很自然的導(dǎo)致一個(gè)遞歸演算法！

遞歸的概念直接或間接地調(diào)用自身的演算法稱為遞歸演算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時(shí)應(yīng)用在演算法設(shè)計(jì)之中，並由此產(chǎn)生許多高效演算法。下麵來看幾個(gè)實(shí)例例1階乘函數(shù)

階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算後得出結(jié)果。intfactLoop(intn){ intk,f; k=1; f=1;

while(kn) {

intf=f*k;

intk=k+1; } returnf;}intfactRec(intn){if(n==0) return1;else returnn*factRec(n-1);}例2Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地得到：intfib(intn){

if(n<=1)

return1;else

return

fib(n-1)+fib(n-2);}intfib(intn){ intf,f1,f2; if(n<=1) f=n; else { f1=fib(n-1);

f2=fib(n-2); f=f1+f2; } returnf;}fibn:3f1:1f2:1f:2fibn:0f1:f2:f:0fibn:1f1:f2:f:1fibn:2f1:1f2:0f:1fibn:1f1:f2:f:1creationis

inpreorder例3Hanoi塔問題設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，並仍按同樣順序疊置。在移動圓盤時(shí)應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個(gè)圓盤；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。在問題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個(gè)問題:voidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}T(1)=1T(n)=2T(n-1)+1T(n)=2T(n-1)+12T(n-1)=4T(n-2)+24T(n-2)=8T(n-3)+4…….2n-2T(2)=2n-1T(1)+2n-2T(n)=2n-1遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明演算法的正確性，因此它為設(shè)計(jì)演算法、調(diào)試程式帶來很大方便。缺點(diǎn)：遞歸演算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是佔(zhàn)用的存儲空間都比非遞歸演算法要多。解決方法：在遞歸演算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸演算法。1、採用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實(shí)現(xiàn)遞歸函數(shù)。3、通過變換能將一些遞歸轉(zhuǎn)化