算法设计与分析课件

演算法設計與分析

第1章演算法問題求解基礎學習要點：理解演算法的概念。理解什麼是程式，程式與演算法的區別和內在聯繫。章節內容：1.1演算法概述1.3演算法設計與分析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. ——演算法是對某個問題求解方案的完整而明確的描述，是指令的有限序列。Fiveimportantfeatures:Finiteness——有窮性（演算法必須總能在執行有限步之後終止）Definiteness——確定性（組成演算法的每一條指令都是清晰，無歧義的）Input——輸入（演算法有零個或多個外部提供的輸入量）Output——輸出（演算法至少產生一個輸出量）Effectiveness——可行性（演算法的每一條指令必須足夠基本，能夠通過已經實現的基本運算執行有限次來實現）“電腦科學是一門研究演算法的科學”演算法與程式

程式(Program)是演算法用某種程式設計語言的具體實現。

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

例如：

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

歐幾裏德演算法（輾轉相除法）：

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

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

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

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

輸出m結束Y流程圖描述：偽代碼描述：1.r=n%m;2.迴圈直到r等於02.1n=m;2.2m=r;2.3r=n%m;3.輸出m;程式設計語言描述（遞歸）：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;}程式設計語言描述（迭代）：可見：一個問題可以設計不同的演算法來求解。同一個演算法可採用不同的形式來表示。程式1-3連續整數檢測intGcd(intm,intn){ if(m==0)returnn; if(n==0)returnm; intt=m>n?n:m;

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

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

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

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

m*n/Gcd(m,n)如何求最小公倍數？演算法的重要性（AlgorithmEverywhere）ApplicationsHumanGenomeProject:identifying100000genesinhumanDNA,determiningthesequencesofthe3billionchemicalbasepairsthatmakeuphumanDNA,storingthisinformationindatabases,anddevelopingtoolsfordataanalysis.（卡普Karp->華盛頓）Internetservice:e.g.routingthedataElectroniccommerce:public-keycryptographyanddigitalsignaturesSystemsHardwareOperatingsystemsCompilers（克努特Knuth-LR(k)文法）假設某一負責人交給你一個很難的任務，幾天後詢問你問題解決了沒有。可能會發生如下圖這樣的情況：問：“交給你的問題，解決方案設計出來了嗎？”答：“我找不到一個有效的演算法來解決它，沒能完成任務。”問：“交給你的問題，解決方案設計出來了嗎？”答：“我找不到一個有效的演算法來解決它，因為這樣的演算法是不存在的。”不過，要證明一個問題不存在有效演算法，往往跟尋找有效演算法一樣難。問：“交給你的問題，解決方案設計出來了嗎？”答：“我找不到一個有效的演算法來解決它，但不是我不行，因為所有這些名人也都找不到解決它的有效演算法。”PhilosophyofProblemSolvingTodealwiththosewhichcan’tbesolved,wecompromise；Todealwiththosewhichcanbesolved,wetryourbest；Todistinguishbetweenthetwoclasses,weuseourwit.演算法與圖靈獎

——超過1/3的Turing獎獲獎者其成果與演算法有關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

演算法與圖靈獎

——超過1/3的Turing獎獲獎者其成果與演算法有關有趣的演算法問題背包問題1（物品可分割）：

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

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

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

①一般解法：用鏈表實現②數學解法：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);

}有趣的演算法問題皇后問題（回溯法經典問題）

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

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

）

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

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

好演算法的4個重要特徵：Correctness——正確性注意區分“正確性”和“健壯性”的概念：演算法正確性——在合法的輸入下，演算法應實現預先規定的功能和計算精度要求。程式健壯性——當輸入不合法的數據時，程式應能做適當處理而不至於引起嚴重後果。正確性和健壯性互相補充。程式可靠性——在正常情況下能正確地工作，在異常情況下也能做出適當處理。2.1演算法複雜度

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

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

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

isalowerboundforaclassofalgorithm.

(lowerbound)

IfWA=F,then

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

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

其中n是問題的規模（輸入大小）演算法複雜度HowtoMeasure?

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

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

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

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

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

A(n)=Tavg(n)

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

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

return

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

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

當n→∞時，有(T(n)-t(n))/T(n)→0。

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

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

如果存在正常數c和自然數n0，使得當n

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

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

上界記號O舉例：C0=O(1) f(n)=C0為非零常數，取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)表示常數計算時間，代表演算法只需執行有限個程式步。如何證明？證明見P22

（定理2-1）如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多項式，且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}可以通過考察一個程式中關鍵操作（keyoperation）的執行次數，來估算演算法的漸近時間複雜度。關鍵操作！執行次數n和總的程式步2n+3有相同的漸近時間複雜度O(n)。關鍵操作通常是位於演算法最內層迴圈的程式步（或語句），是演算法中執行次數最多的操作（程式步）。可以通過考察一個程式中關鍵操作（keyoperation）的執行次數，來估算演算法的漸近時間複雜度。關鍵操作通常是位於演算法最內層迴圈的程式步（或語句），是演算法中執行次數最多的操作（程式步）。例如：程式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}關鍵操作！執行次數n3和總的程式步2n3+3n2+2n+1有相同的漸近時間複雜度O(n3)。可以通過考察一個程式中關鍵操作（keyoperation）的執行次數，來估算演算法的漸近時間複雜度。關鍵操作通常是位於演算法最內層迴圈的程式步（或語句），是演算法中執行次數最多的操作（程式步）。例如：程式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;}有時候演算法時間的計算並非直截了當，while迴圈每次迭代後餘數值並非按常數因數遞減。如何計算迭代次數？定理2-2如果n>m，則nmodm<n/2。每次迭代的餘數最多是原始值的一半，因此迭代次數為O(logn)。歐幾裏德演算法的時間複雜度為O(logn+logm)。（2）漸近下界記號

如果存在正常數c和自然數n0，使得當n

n0時有f(n)≥cg(n)，則稱函數f(n)當n充分大時有下界，且g(n)是它的一個下界，記做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次多項式，且am>0，則f(n)=Ω(nm)。（3）緊漸近界記號

如果存在正常數c1,c2和n0，使得當n

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

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

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

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

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

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

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

如果對於任何正常數c>0都存在正整數n0>0，使得當n

n0時有f(n)＜cg(n)（等價於:n

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

如果對於任何正常數c>0都存在正整數n0>0，使得當n

n0時有f(n)＞cg(n)（等價於n

時，f(n)/g(n)

），則稱函數f(n)當n充分大時的階比g(n)高，記做f(n)＝

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

g(n)=

(f(n))

漸近分析中函數比較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))

，存在正常數c1和自然數n1，使得對所有n

n1，有f1(n)

c1f(n)。 類似地，對於任意g1(n)

O(g(n))

，存在正常數c2和自然數n2，使得對所有n

n2，有g1(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;}時間複雜度綜合分析（例1）（1）最壞情況下：Tmax(n)=max{T(I)|size(I)=n}=O(n)（2）最好情況下：Tmin(n)=min{T(I)|size(I)=n}=O(1)（3）平均情況下，假設：搜索成功的概率為p(0

p

1)；在數組的每個位置i(0

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

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

if語句計算時間和else語句計算時間的較大者。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

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

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

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

補充：C/C++知識點復習用c++描述演算法（1）選擇語句：1.1if語句：1.2？語句：

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

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）跳轉語句：3.1return語句：

returnexpression;3.2goto語句：

gotolabel;

label:（4）函數：例：

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

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

運算符new用於動態存儲分配，返回一個指向所分配空間的指針。 例：int

y；y=newint；

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

int

y=newint；

y=10； 或 int

y=newint(10)； 或 int

y；y=newint(10)；

為了在運行時創建一個大小可動態變化的一維浮點數組x，可先將x聲明為一個float類型的指針。然後用new為數組動態地分配存儲空間。例：float

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

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

當動態分配的存儲空間已不再需要時應及時釋放所佔用的空間。用運算符delete來釋放由new分配的空間。 例：deletey；

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

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

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

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

2-10 2-13(更正）關鍵：根據遞歸過程建立遞推關係式，然後求解這個遞推關係式。猜測技術:

對遞推關係式估計一個上限，然後（用數學歸納法）證明它正確。附錄：遞歸演算法2.擴展遞歸技術

îíì>+==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的原問題分成若干個大小為n/b的子問題，其中a個子問題需要求解，而cnk是合併各個子問題的解需要的工作量。

îíì>+==1)(1)(ncnbnaTncnTkïîïíì<=>=kkkbkkabanObannObanOnTb)()log()()(log附錄：漸近分析記號的若干性質（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）算術運算：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(n)=O(f(n))

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

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

x

：不大於x的最大整數；

x

：不小於x的最小整數。

x-1<x

x

x<x+1；

n/2

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

對於正整數m,n和實數a>0）

(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1

an為單調遞增函數;

a>1

nb=o(an)

對數函數

logn=log2n;

lgn=log10n;

lnn=logen;

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

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

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

分治法所能解決的問題一般具有以下幾個特徵：該問題的規模縮小到一定的程度就可以容易地解決；因為問題的計算複雜性一般是隨著問題規模的增加而增加，因此大部分問題滿足這個特徵。分治法的適用條件

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

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

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

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

階乘函數可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數的二個要素，遞歸函數只有具備了這兩個要素，才能在有限次計算後得出結果。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數列無窮數列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數列。它可以遞歸地定義為：邊界條件遞歸方程第n個Fibonacci數可遞歸地得到：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塔問題設a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現要求將塔座a上的這一疊圓盤移到塔座b上，並仍按同樣順序疊置。在移動圓盤時應遵守以下移動規則：規則1：每次只能移動1個圓盤；規則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規則3：在滿足移動規則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。在問題規模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術來解決這個問題: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遞歸小結優點：結構清晰，可讀性強，而且容易用數學歸納法來證明演算法的正確性，因此它為設計演算法、調試程式帶來很大方便。缺點：遞歸演算法的運行效率較低，無論是耗費的計算時間還是佔用的存儲空間都比非遞歸演算法要多。解決方法：在遞歸演算法中消除遞歸調用，使其轉化為非遞歸演算法。1、採用一個用戶定義的棧來模擬系統的遞歸調用工作棧。該方法通用性強，但本質上還是遞歸，只不過人工做了本來由編譯器做的事情，優化效果不明顯。2、用遞推來實現遞歸函數。3、通過變換能將一些遞歸轉化