算法設計基本方法（2）歸納法：通過分析少量特殊狀況，找出關系，得到結論例：搏彩問題這期彩票該買幾呢？第一期3十一2二5十二1三6十三1四8十四0五9十五2六8十六2七7十七3八5十八4九5十九4十3二十4依據曲線，買5比較好歸納法特點：適用面廣，高效運用，常能解決很多實際問題適用范圍：樣本空間有確定規律，多用于預料領域，數據難以獲得的工程計算科學計算等領域缺點：歸納出的數學模型須要證明，且代碼實現不規范改進方法：常接受不同歸納方法共同求解一個問題軟肋：不能求解樣本空間過于零散的問題算法設計基本方法（3）遞推從已知的初始條件動身，逐次推出所要求的各中間結果和最終結果特點：接受遞推關系式數學模型，理論正確性得到保證，由于遞推關系式來源于歸納，所以本質上屬于歸納法適用范圍：數值計算等工程應用缺點：需考慮數值計算中穩定性問題，易產生蝴蝶效應軟肋：無遞推關系式的問題不行解NYBJ遞推 據說，美軍1910年的一次部隊的吩咐傳遞是這樣的:

營長對值班軍官:明晚大約8點鐘左右，哈雷彗星將可能在這個地區看到，這種彗星每隔76年才能望見一次。吩咐全部士兵著野戰服在操場上集合，我將向他們說明這一罕見的現象。假如下雨的話，就在禮堂集合，我為他們放一部有關彗星的影片。值班軍官對連長:依據營長的吩咐，明晚8點哈雷彗星將在操場上空出現。假如下雨的話，就讓士兵穿著野戰服列隊前往禮堂，這一罕見的現象將在那里出現。連長對排長:依據營長的吩咐，明晚8點，非凡的哈雷彗星將身穿野戰服在禮堂中出現。假如操場上下雨，營長將下達另一個吩咐，這種吩咐每隔76年才會出現一次。排長對班長:明晚8點，營長將帶著哈雷彗星在禮堂中出現，這是每隔76年才有的事。假如下雨的話，營長將吩咐彗星穿上野戰服到操場上去。班長對士兵:在明晚8點下雨的時候，著名的76歲哈雷將軍將在營長的陪伴下身著野戰服，開著他那“彗星”牌汽車，經過操場前往禮堂。例：計算公式一：記為則初始誤差????!!!Whathappened?!留意此公式精確成立考察第n步的誤差我們有責任改變。造成這種情況的是不穩定的算法/*unstablealgorithm*/迅速積累，誤差呈遞增走勢可見初始的小擾動公式二：留意此公式與公式一在理論上等價。方法：先估計一個IN

,再反推要求的In(n<<N)。可取取

Wejustgotlucky?考察反推一步的誤差：以此類推，對n<N

有：誤差逐步遞減,這樣的算法稱為穩定的算法/*stablealgorithm*/類似例子見教材p8算法設計基本方法（4）遞歸將一個困難的問題歸結為若干個較簡潔的問題，然后將這些較簡潔的每一個問再歸結為更簡潔的問題，這個過程可以始終做下去，直到最簡潔的問題為止。例：計算階乘:n!=n(n1)21,0!=1.intfactorial(intn){inti,result;result=1;if(n>0){for(i=1;i<=n;i++)result=result*i;}/*endif*/returnresult;}intfactorial(intn){if(n>0)returnn*factorial(n1);elsereturn1;}例:斐波那契(Fibonacci)序列：

F0=F1=1Fi=Fi-1+Fi-2

（i>1)

算法求斐波那契數

intF(n){//返回第n個斐波那契數//intn;if(n<=1)return(1);elsereturnF(n-1)+F(n-2);}算法效率：對F(n-1)、F(n-2)存在大量的重復計算改進：保存中間結果例:歐幾里得算法已知兩個非負整數a和b，且a＞b≥0，求這兩個數的最大公因數。輾轉相除法：若b=0，則a和b的最大公因數等于a；若b＞0，則a和b的最大公因數等于b和用b除a的余數的最大公因數。算法求最大公因數

GCD(inta,intb)//約定a>b//{if(b==0)return(a);elsereturn(GCD(b,a%b));}

例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;遞歸特點：結構清晰，可讀性強，簡潔用數學歸納法證明算法正確性適用范圍：難以用循環或遞推直觀描述的困難問題缺點：資源耗費多，執行效率低，所以在算法優化時接受消遞歸策略算法設計基本方法（5）減半遞推技術（分治法）所謂“減半”，是指將問題的規模減半，而問題的性質不變。所謂“遞推”，是指重復“減半”的過程。例：二分法求方程實根的減半遞推過程（算法及程序見書p13）首先取給定區間的中點c＝(a＋b)/2。然后推斷f(c)是否為0。若f(c)＝0,則說明c即為所求的根，求解過程結束；假如f(c)≠0,則依據以下原則將原區間減半：若f(a)f(c)＜0，則取原區間的前半部分；若f(b)f(c)＜0，則取原區間的后半部分。最終推斷減半后的區間長度是否已經很小：若|a－b|＜ε，則過程結束，取(a＋b)/2為根的近似值；若|a－b|≥ε，則重復上述的減半過程。例二分檢索

二分檢索：每次選取中間元素的下標算法二分檢索IntBINSRCH(intA[],intn,intx){intlow,high,mid;low=1;high=n;while(low<=high){

mid=if(x<A[mid])high=mid-1;if(x>A[mid])low=mid+1;elsereturnmid;}return0;}注：給定一個按非降次序排列的元素數組A(1:n)，n≥1,推斷x是否出現。若是，返回當前角標mid若非，返回0，表示沒有找到例：設A(1:9)=(-15，-6，0，7，9，23，54，82，101)

在A中檢索x=101，-14，82。執行軌跡見下表1表1運行軌跡示例x=101x=-14x=82lowhighmidlowhighmidlowhighmid19519519569714269789811189899921找不到找到

找到

成功的檢索不成功的檢索成功的檢索遞推減半技術特點：快速縮小計算規模適用范圍：工程計算，矩陣計算，數值計算中能夠快速將問題分治的狀況算法設計基本方法（6）回溯法通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步摸索，對于每一步的摸索，若摸索成功，就得到問題的解，若摸索失敗，就逐步回退，換別的路途再進行摸索。例：八皇后問題（教材p15）迷宮問題事實上是一種圖的深度優先遍歷的方法特點：算法效率高，直觀清晰適用范圍：適用于解決“是否存在”或者“有多少種可能”問題缺點：算法的困難性與計算依次有關算法分析1.分析算法的目的在于：通過對算法的分析，在把算法變成程序實際運行前，就知道為完成一項任務所設計的算法的好壞，從而運行好的算法，改進差的算法，避開無益的人力和物力奢侈。算法分析是計算機領域的“古老”而“前沿”的課題。

算法分析“好”的算法應當達到以下指標正確性(Correctness):算法應當滿足具體問題的需求可讀性(Readability):算法是連接數學模型和程序的橋梁,可讀性好有助于人對算法的理解健壯性(Robustness):算法對于異樣狀況有充分的考慮和處理方法效率高和存儲量少:時間困難度:指執行算法所須要的計算工作量

算法的工作量＝f(n)空間困難度:執行算法所須要的內存空間n指算法規模時間困難度(1)平均性態(averagebehavior):用各種特定輸入下的基本運算次數的帶權平均值來度量算法的工作量最壞狀況困難性(WorstCaseComplexity)規模在n時,算法所執行的基本運算的最大次數由于最壞狀況困難性給出算法工作量的一個上界,所以更具好用價值時間困難度(2)例:依次搜尋法的時間困難度分析(教材p17) 接受依次搜尋法，在長度為n的一維數組中查找為x的元素。 算法:即從數組的第一個元素起先，逐個與被查值x進行比較。基本運算:x與數組元素的比較。平均性態分析:最壞狀況分析:W(n)＝max{ti|1≤i≤n＋1}＝n如何進行算法分析？對算法進行全面分析，可分兩個階段進行：事前分析：求算法的一個時間/空間限界函數，即通過對算法的“理論”分析，得出關于算法時間和空間特性的特征函數（Ο、Ω）——與計算機物理軟硬件沒有干脆關系。事后測試：將算法編制成程序后實際放到計算機上運行，收集其執行時間和空間占用等統計資料，進行分析推斷——干脆與物理實現有關。1）事前分析目的：試圖得出關于算法特性的一種形式描述（限界函數），以“理論上”衡量算法的“好壞”。如何給出反映算法特性的描述？統計算法中各種運算的執行狀況，包括：引用了哪些運算每種運算被執行的次數該種運算執行一次所花費的時間等。算法的執行時間=∑fi*ti工作量

工作量：算法中語句或運算的執行次數。

例：

x=x+yfor(i=0;i<n;i++)for(i=0;i<n;i++)

x=x+yfor(j=0;j<n;j++)

x=x+y(a)(b)(c)

分析：

(a)：x=x+y執行了1次

(b)：x=x+y執行了n次

(c)：x=x+y執行了n2次限界函數的表示就計算時間而言，事前分析階段求得算法在工作量上的算法規模n的函數稱為限界函數，記為：g(n)限界函數以算法中主要運算單元為基本運算統計運算次數的數量級★g(n)的一般形式：關于n的簡潔函數式g(n)用以限界，因此只接受所得到計算次數的最高次項表示：隨著n（規模）的增大，多項式函數式的最高次項的變更能夠最顯著的反映整個多項式的變更★不同的算法，g(n)的具體形式是不同的，常用的限界函數有：1；logn；n；nlogn；n2；n3；nm；2n；n！；nn等

2）事后測試目的：運行程序，統計執行實際耗費的精確的時間與空間，與事前分析的結論進行比較，驗證從前的分析結論——包括正確性、執行性能等，比較、優化所設計的算法。分析手段：作時、空性能分布圖計算時間的漸近表示記：算法的實際計算時間為f(n)，計算時間的限界函數為g(n)其中，n是輸入或輸出規模的某種測度。f(n)表示算法的“實際”執行時間—與機器及語言有關。g(n)是事前分析的結果——一個形式簡潔的函數，如nm，logn，2n，n!等。是與工作量有關、而與機器及語言無關的函數。

以下給出算法執行時間：上界（О）、下界（Ω）、“平均”（）的定義。1）上界函數定義1假如存在兩個正常數c和n0，對于全部的n≥n0，有|f(n)|≤c|g(n)|則記作f(n)=Ο(g(n))

含義：假如算法用n值不變的同一類數據在某臺機器上運行時，所用的時間總是小于|g(n)|的一個常數倍。所以g(n)是計算時間f(n)的一個上界函數。f(n)的數量級就是g(n)。試圖求出最小的g(n)，使得f(n)=Ο(g(n))。數量級——衡量工作量的“大小”的一種測度，通過f(n)的上界函數g(n)確定語句的數量級：語句的執行次數例：1，n，n2算法的數量級：算法所包含的全部語句的執行次數之和。數量級反映了算法困難度的最本質的特征。例：假如求解同一個問題的三個算法分別具有n，n2，n3數量級。次數若n=10，則可能的執行時間將分別是10，100，1000個單位時間——與環境因素無關。計算時間的數量級的大小對算法有確定性的影響例：假設解決同一個問題的兩個算法，它們都有n個輸入,計算時間的數量級分別是n2和nlogn。則，n=1024：分別須要1048576和10240次運算。n=2048：分別須要4194304和22528次運算。分析：★同等規模下的計算量比較：★規模增大狀況下的比較：在n加倍的狀況下，一個Ο(n2)的算法計算時間增長4倍，而一個Ο(nlogn)算法則只用兩倍多一點的時間即可完成。多項式時間算法和指數時間算法多項式時間算法：可用多項式（函數）對其計算時間限界的算法。常見的多項式限界函數有：Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數時間算法：計算時間用指數函數限界的算法常見的指數時間限界函數：Ο(2n)<Ο(n！)<Ο(nn)說明：當n取值較大時，指數時間算法和多項式時間算法在計算時間上特別懸殊。典型的計算時間函數曲線一般相識當數據集的規模很大時，要在現有的計算機系統上運行具有比Ο(nlogn)困難度還高的算法是比較困難的。指數時間算法只有在n取值特別小時才好用。要想在依次處理機上擴大所處理問題的規模，有效的途徑是降低算法的計算困難度，而不是（僅僅依靠）提高計算機的速度。計算時間函數值比較3s=microsecond=10-6secondsms=millisecond=10-3secondssec=secondsmin=minutesyr=yearshr=hoursd=days常見時間困難度數量級分析（1）常見時間困難度數量級分析（2）2nn2nlognnLognfn定義1.2假如存在兩個