[计算机]演算法简介课件.ppt

1、第二十章第二十章 演算法簡介演算法簡介知己知彼，百戰不貽孫子ij+-12341內容內容n前言前言n20.1 演算法分析演算法分析n20.2 個別擊破策略個別擊破策略n20.3 貪婪策略貪婪策略n20.4 動態規劃動態規劃n20.5 刪除與搜尋策略刪除與搜尋策略n20.6 課後習題課後習題n20.7 欲罷不能欲罷不能2前言前言演算法(Algorithm)n電腦上解決問題的方法n包括明確的輸出入資料和詳細且有限的執行步驟n了解每個演算法在不同狀況下所花的時間，而從中挑選適合的演算法以迅速得到答案n演算法設計策略320.1 演算法分析演算法分析在電腦上解決問題的基本架構在電腦上解決問題的基本架構n演

2、算法以程式描述後在電腦上執行，資料輸入至程式後，經過程式對資料的運算，最後產生解答資料演算法（程式）圖 20.1解答4時間複雜度時間複雜度(Time Complexity)n假設演算法 A 能解問題Pn問題P的輸入資料量為Nn假設資料量為N的資料樣本(Data Instance)有 D1,D2,.,Di,.,Dm 共 m 種n令 T(Di)表示當輸入資料為 Di 時演算法 A 要執行的運算或步驟的總次數n演算法 A 的最好狀況時間複雜度最好狀況時間複雜度(Best-Case Time Complexity)n T(Di)(1 i m)中最小的值，即min1 i m T(Di)5時間複雜度時間複

3、雜度(cont.)n演算法 A 的最差狀況時間複雜度最差狀況時間複雜度(Worst-Case Time Complexity)n T(Di)(1 i m)中最大者，即max1 i m T(Di)n演算法A的一般狀況時間複雜度一般狀況時間複雜度(Average-Case Time Complexity)nT(Di)(1 i m)的平均值或期望值(在某機率假設下)n說“演算法A的時間複雜度為C”就是指其最差狀況時間複雜度為C6時間複雜度時間複雜度(cont.)範例n若問題P之輸入資料量為 N 的樣本有D1,D2,D3 三種，且 T(D1)=3,T(D2)=N,T(D3)=N3 n演算法 A 的 最

4、好狀況時間複雜度為 3 n演算法 A 的最差狀況為 N3n演算法 A 的一般狀況為(3+N+N3)/3 n稱演算法 A 的時間複雜度為 N37漸近上限漸近上限(Asymptotic Upper Bound)O階次階次n如果存在某固定正實數 c 及某個非負整數 m 使得對所有的 n m，不等式 g(n)c f(n)都成立，則 g(n)=O(f(n)，稱 f(n)為 g(n)的漸近上限 Example:nN2+10N=O(N2)，因為當n 10 時，N2+10N 2N2n稱N2為N2+10N的漸進上限8漸近下限漸近下限(Asymptotic Lower Bound)階次階次n若存在某固定正變數 c

5、 及某非負整數 m 使得對所有 n m，不等式 g(n)c f(n)都成立，則 g(n)=(f(n)，稱 f(n)為 g(n)的漸近下限 Examplenn3=(n2)，因為當n 1時，n31 n2，所以n2為n3的漸近下限。9真正階次真正階次(Exact Order)n若存在某固定正變數 c 及某非負整數 m 使得對所有 n m，不等式 g(n)c f(n)都成立，則 g(n)=(f(n)，稱 f(n)為 g(n)的漸近下限 ExamplenN2+10N=(N2)，因為 N2+10N=O(N2)且 N2+10N=(N2)。10真正階次真正階次(cont.)n當n足夠大時，2n n3 n2 n

6、logn n lognf(n)n2nn3n2nlognNlogn121101024840.60205999120.30102999641664162.40823996540.6020599918256512647.22471989680.9030899871665536409625619.26591972161.20411998332429496729632768102448.16479931321.505149978641.84467E+192621444096115.5955183641.8061799741283.40282E+38209715216384269.72287611282.

7、107209972561.15792E+771677721665536616.50943112562.4082399655121.3408E+1541342177282621441387.146225122.70926996111指數函數分析指數函數分析指數函數(Exponential Function)n例如：f(n)=cp(n)，其中c為常數，p(n)為n的多項式函數(Polynomial Function)(如n，n2+10，log2n，nlog2n)nExample:2n、3n、4logn等函數n函數值上升速度相當快時間複雜度為指數函數階次的演算法在資料量足時間複雜度為指數函數階次的演

8、算法在資料量足夠多時需要相當長的時間才能解得答案夠多時需要相當長的時間才能解得答案12多項式時間演算法多項式時間演算法(Polynomial-Time Algorithm)n時間複雜度是O(p(n)的演算法，其中p(n)為n的多項式函數電腦上可解電腦上可解（Tractable）的問題的問題n能用多項式時間演算法解得答案的問題，即能用電腦在合理時間內求得答案n例如：排序及搜尋等問題13排序法及搜尋法的時間複雜度排序法及搜尋法的時間複雜度 時間複雜度演算法最好狀況最差狀況插入排序O(n)O(n2)氣泡排序O(n)O(n2)謝耳排序O(n)O(n2)兩兩合併排序O(n)O(nlog2n)循序搜尋O(

9、1)O(n)二分搜尋O(1)O(log2n)14最佳演算法最佳演算法(Optimal Algorithm)n若可解問題P的演算法A的時間複雜度為t，而解問題P的演算法最少需要t時間，則稱演算法A是解問題P的最佳演算法最佳演算法 n例如：兩兩合併排序法是最佳排序演算法n排序n個數的問題最少需要O(nlog2n)時間n兩兩合併排序法的時間複雜度是O(nlog2n)15難解問題難解問題(Intractable Problem)n若問題P無法以多項式時間演算法解得答案，則問題P無法於電腦上在合理時間內求得答案，稱問題P為難解問題，或NP-Complete問題Examplen旅行推銷員問題(Travel

10、ling Salesman Problem)n圖形塗色問題(Graph-Coloring Problem)n裝箱問題(Bin-Packing Problem)1620.2 個別擊破策略個別擊破策略(Divide-and-Conquer Method)n將原來的問題P分解成2個或多個子問題n待個別解決這些子問題後再經由合併(merge)處理整理出原來問題的答案n因為分割後的子問題是資料量較小的問題P，因此解子問題時又可遞迴應用上述的方法經由分割及合併的過程得到解答nExample:二分搜尋法，兩兩合併排序法17兩兩合併排序法兩兩合併排序法n一開始就將資料分割成兩部份處理，然後再遞迴細分各資料直至

11、不能細分為止n接著就兩兩合併成排序的序列，慢慢的將分割的資料合併成排序的序列，最後得到所有資料的排序結果1062717324556106271732455610627173245561062717324556610172743256561017274532564561017273256分割分割分割分割分割分割合併合併合併合併合併合併18二分搜尋法二分搜尋法 n假設陣列D中依序放有4,3,5,2,6,7,1等七個整數，目標是將這些數依小到大順序排序n首先觀察第一個數4在最後排序好的序列中應是第四位即應放在D(4)n如果能將不大於4的數放在D(1)至D(3)中而不小於4的數放在D(5)至D(7)中

12、則只要再分別排序好D(1)至D(3)的數及D(5)至D(7)內的數那原來排序問題就解決了19二分搜尋法二分搜尋法(cont.)方法n令i=2j=7n從D(i)開始向右找到第一個不小於D(1)的數以i記錄其陣列的索引n從D(j)開始向左找到第一個不大於D(1)的數以j記錄其陣列索引n若i N THEN3 I=M4 J=N+15 K=D(M)6 DO7 DO8 I=I+19 LOOP UNTIL D(I)=K10 DO11 J=J-112 LOOP UNTIL D(J)=K13 IF I J THEN14 K=D(I)15 D(I)=D(J)16 D(J)=K17 ELSE18 EXIT DO19

13、 END IF20 LOOP21 K=D(M)22 D(M)=D(J)23 D(J)=K24 QSORT(M,J-1)25 QSORT(J+1,N)26END IF27END SUB23快速排序法快速排序法(cont.)快速排序法n最差時間複雜度為O(n2)，其中n為資料個數 n一般狀況時間複雜度為O(nlog2n)個別擊破策略常用於計算幾何個別擊破策略常用於計算幾何(Computational Geometry)的應用問題的應用問題2420.3 貪婪策略貪婪策略(Greedy Method)n每次的決策都是朝向目前“最好”的方向前進n櫃檯服務問題n某一個銀行出納櫃檯要服務n位顧客，銀行的目標

14、是希望顧客在櫃檯等待的平均時間要最少n解決之道是每次都從尚未服務的顧客中，選擇需要服務時間最短的顧客來服務，如此就可達到預期目標25貪婪策略貪婪策略-實例說明實例說明n假設有5個顧客A，B，C，D，E幾乎同時到達銀行櫃檯，其所需服務時間如表所示n銀行櫃檯將依序服務B，D，E，C，An顧客在櫃檯等待的平均時間為 1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)/5=7 顧顧 客客服服 務務 時時 間間A 5B 1C 4D 2E 326背包問題背包問題(Knapsack Problem)n假設有多個可分解的物件和一只限重W的背包n每件物件有其重量及其被選取放入背包內的利益

15、n請問要如何將物件放進背包內而使得獲得的利益最大n解決的方法：n是每次在限重的情形下，選取尚未放入的物件中擁有最大的利益與重量的比值之物件放入背包內。27背包問題背包問題-實例說明實例說明n設背包限重100，有A，B，C，D，E共五個物件，其資料如表所示物件物件重量重量利益利益利益利益/重量重量A10202.0B20301.5C30662.2D40401.0E50601.228背包問題背包問題-實例說明實例說明(cont.)解法n依利益/重量由大至小順序放入物件，即C,A,B,E,D順序考慮物件物件個數個數累計利益累計利益累計重量累計重量C16630A18640B111660E0.816410

16、029最小擴展樹最小擴展樹(Minimum Spanning Tree)右圖n由頂點(Vertex)及邊(Edge)構成n每一邊都連接兩頂點，可指定其加權(Weight)，分有向和無向兩種n圓圈代表頂點n連接兩頂點的線為邊n每個邊都有非負的加權 n例如頂點V3與頂點V5間的邊之加權為5 31456872V2V3V1V4V530最小擴展樹最小擴展樹(cont.)n無向圖(Undirected Graph)：均是無方向邊的圖形。n無向圖的路徑(Path)：由頂點構成的序列，其中序列裏每個頂點與其後一個頂點之間必有邊相連n例如V1,V5,V2是一條從頂點V1到頂點V2的路徑。n聯通圖(Connect

17、ed Graph)：任兩頂點都存在一條路徑的無向圖n例如右圖是聯通圖31456872V2V3V1V4V531最小擴展樹最小擴展樹(cont.)n迴圈(Cycle)：從某頂點出發回到該頂點的路徑 n例如V1,V5,V2,V1路徑就是迴圈n無迴圈圖(Acyclic Graph)：沒有迴圈的圖形n樹(Tree)：聯通的無迴圈圖n圖形G=(V,E)，V是頂點所成的集合，E是邊所成的集合31456872V2V3V1V4V532最小擴展樹最小擴展樹(cont.)n圖形G=(V,E)的擴展樹T=(V,E)是包括所有G的頂點的樹，其中E是E的子集合。n例如圖(a)及(b)都是右上圖的擴展樹31456872V2

18、V3V1V4V53157V2V3V1V4V53162V2V3V1V4V5(a)(b)33最小擴展樹最小擴展樹(cont.)n擴展樹T=(V,E)的加權：集合E中所有的邊的加權的總和n例如圖(a)的擴展樹加權為1+3+5+7=16，而圖(b)的擴展樹加權為1+2+3+6=12。n最小擴展樹問題：求出給定的聯通且加權的無向圖之最小擴展樹n圖形G的最小擴展樹就是擁有最小加權的擴展樹n如圖(b)的擴展樹是右上圖的最小擴展樹3157V2V3V1V4V53162V2V3V1V4V5(a)(b)31456872V2V3V1V4V534Kruskal演算法演算法nKruskal演算法：依據邊的加權由小到大的順

19、序考慮該邊是否為最小擴展樹的邊n步驟1：將圖形G=(V,E)所有的邊依其加權由小到大排好，依序為e1,e2,e3,em。n步驟2：建立圖形T=(V,E)，其中 E=。設i=1。n步驟3：若ei加入圖形T中不產生迴圈，則將ei加入圖形T，即E=E ei；否則，i=i+1。n步驟4：若圖形T不是圖形G的擴展樹，則重複步驟3；否則，圖形T是圖形G的最小擴展樹，結束演算法執行。35Kruskal演算法實例說明演算法實例說明31456872V2V3V1V4V536最短路徑問題最短路徑問題(Shortest Path Problem)n下圖是S、A、B、T四個地點的交通路線，各路線分別標上距離n令D(a,

20、b)表示從a到b的最短路徑長度n可知D(S,T)=D(S,A)+D(A,B)+D(B,T)=10+15+20=45n利用貪婪策略就能得到答案SA104025BT156020305037最短路徑問題最短路徑問題(cont.)n若要找下圖的D(S,T)，則D(S,T)=24+20=44，此結果並不等於D(S,A)+D(A,B)+D(B,T)=45n以動態規劃策略找一般圖形的最短路徑SA104025BT1560203050243820.4 動態規劃動態規劃1.個別擊破策略1.是遞迴地將問題分成較小的問題後分別求得解答，然後合併這些部份答案成為完整的答案2.由上至下(Top-Down)的計算策略nFi

21、bonacci函數f(n)：n f(0)=0n f(1)=1n f(n)=f(n-1)+f(n-2)，n 239以個別擊破策略計算以個別擊破策略計算f(5)n過程如下圖所示n其中f(3)f(2)f(1)f(0)被重複計算許多次n如果能先依序將f(0)f(1)f(2)f(3)f(4)的結果計算出來，就可避免重複計算，增進計算速度。f(5)f(4)f(2)f(3)f(2)f(1)f(1)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)40以個別擊破策略計算以個別擊破策略計算f(5)(cont.)n以陣列FIB儲存Fibonacci函數利用下面的方法計算f(n)：FIB(0)=0 F

22、IB(1)=1 FOR I=2 TO n FIB(I)=FIB(I-1)+FIB(I-2)NEXT I41動態規劃動態規劃(Dynamic Programming)策略策略n將問題分成小問題然後直接解小問題將結果儲存起來以備之後使用n由下至上(Bottom-Up)計算策略42二項式係數二項式係數(Binomial Coefficient)nB(n,k)=n!/(k!(n-k)!)n當nk的值不小時難計算n!及k!n計算速度慢nB(n,k)=B(n-1,k-1)+B(n-1,k)if 0 k n 1if k=0 or k=nn以動態規劃策略計算之43二項式係數二項式係數(cont.)以動態規劃策

23、略計算B(n,k)n令陣列BI是一個二維陣列有n+1個列(編號從0至n)k+1個欄(編號從0到k)n將B(n,k)的值儲存於BI(n,k)內 FOR I=0 TO n FOR J=0 TO mini,k IF J=0 OR J=I THEN BI(I,J)=1 ELSE BI(I,J)=BI(I-1,J-1)+BI(I-1,J)END IF NEXT J NEXT I 44有向圖的最短路徑問題有向圖的最短路徑問題(Shortest Path Problem)n找出在有向及非負加權的圖形上任兩頂點的最短路徑。n圓圈代表頂點n連接兩頂點的線稱為邊n每個邊都有方向也有對應的非負的加權 n有向圖的路徑

24、是一個頂點序列，其中序列裏每個頂點到其後一個頂點的邊一定存在n例如V1,V3,V2就是一條從頂點V1至頂點V2的路徑。n路徑的長度為路徑上所有的邊的加權的和n例如路徑V1,V3,V2的長度為6+4=10。2V1V2741V3V4563145有向圖的最短路徑問題有向圖的最短路徑問題(cont.)n假設圖形有n個頂點分別是V1,Vn。n令dk(i,j)表示只有經過集合V1,V2,Vk中某頂點的Vi到Vj的最短路徑長度n令d0(i,j)為Vi到Vj的邊的加權n經過集合V1,Vk中某些頂點的Vi到Vj最短路徑可能不經過Vk也可能經過Vkn如果不經過Vk則dk(i,j)=dk-1(i,j)；n如果經過V

25、k，則dk(i,j)=dk-1(i,k)+dk-1(k,j)ndk(i,j)=mindk-1(i,j),dk-1(i,k)+dk-1(k,j)46有向圖的最短路徑問題有向圖的最短路徑問題(cont.)d01234d11234101621016221021073354035407437043470d21234d312341016210162210732107335407354074347043470d41234101622107335407434702V1V2741V3V4563147有向圖的最短路徑問題有向圖的最短路徑問題(cont.)n假設Vi到Vj的最短路徑經過Vk則Vi到Vk的路徑也是最

26、短的路徑而Vk到Vj的路徑也是最短的。n例如由V2到V4的最短路徑為V2,V1,V4而路徑V2,V1也是V2到V1的最短路徑而路徑V1,V4也是V1到V4的最短路徑n最佳解包含其組成份子的最佳解之特性稱為最佳最佳化原則化原則(Principle of Optimality)n如果最佳化問題能應用此最佳化原則則可以用動態規劃策略設計遞迴運算式來求得最佳解4820.5 刪除與搜尋策略刪除與搜尋策略(Prune-and-Search Method)n包含多次的處理，每次的處理都會將輸入資料刪除固定的百分比，並運用同樣的方法遞迴地以刪除後的資料當作輸入資料重新解問題，經過若干次處理後，資料量將可縮小到

27、能用固定常數的時間解得答案nExample：二元搜尋法的每個步驟能去除一半的資料，是典型的刪除與搜尋演算法49刪除與搜尋策略刪除與搜尋策略(cont.)找出 n 個數的第 k 小的數n直接的解法：將這 n 個數由小到大排好後，然後就能依序找出第 k 小的數nO(nlog2n)時間。n刪除與搜尋策略：O(n)時間50刪除與搜尋策略刪除與搜尋策略-範例範例假設 n 為 5 的倍數n步驟 1：將此 n 個數，分成 n/5 個數堆,每堆 5 個數。n步驟 2：分別將各數堆排序。n步驟 3：令 P 為數堆中間值的中間值。n步驟 4：令 S1 為小於 P 的數所成的集合，S2為等於 P 的數所成的集合，S

28、3為大於 P 的數所成的集合。n步驟 5：若 S1 的元素個數大於或等於 K，則丟棄 S2及S3，並繼續利用本演算法找尋 S1 中的第 K 小的數。否則，如果S1 與 S2 的元素個數和大於或等於 K，則 P 為第 K 小數;否則，令 K=K-|S1|-|S2|，丟棄 S1及 S2，並繼續利用本演算法找尋 S3 中的第K小的數51刪除與搜尋策略刪除與搜尋策略-範例範例(cont.)n假設 n=25，經過步驟 1 分成 25/5=5 個數堆後的資料32120112513481511419610716923121722182425圖20.1052刪除與搜尋策略刪除與搜尋策略-範例範例(cont.)

29、n各數堆排序後，此時各數堆的中間值分別為 11,8,10,12,22，而 11 是這些數的中間值。23112021458131516101419791216231718222425圖20.1153刪除與搜尋策略刪除與搜尋策略-範例範例(cont.)n將數堆位置調整後，左上角的矩形部份為 S1 和 S2，而右下角的矩形部份為 S2 和 S323112021458131516101419791216231718222425圖20.12S2S3最少n/4個數S1S2最少n/4個數54刪除與搜尋策略刪除與搜尋策略-範例範例(cont.)n步驟5可能丟棄S2及S3，或丟棄S1及S2，n被丟棄的資料至少為

30、n/4個數n每執行一次此演算法，資料將只剩下n-(n/4)=3n/4個數。n令T(n)表示此演算法在n個數中找第k小的數所需的時間nT(n)=T(3n/4)+O(n)n步驟1至步驟4需O(n)時間n得T(n)=O(n)n刪除與搜尋策略能應用於如雙變數的線性規劃問題、單中心問題等計算幾何問題。5520.6 課後練習課後練習1.以快速排序法完成下列0個數的排序：10,21，5，31，42，24，90，50，15，2。2.假設有面額元、元、元及元郵票。若某郵件需元的郵資，為了讓郵票張數最少，請問這些面額的郵票各需幾張？(提示：貪婪策略)3.分別以O、階次表示下列各函數：a)0.001n2+nb)n+

31、log2nc)2n+nlog2n5620.6 課後練習(cont.)4.請以動態規劃演算法找出下圖任兩頂點的最短路徑：V24V352V171V46215720.6 課後練習(cont.)5.請以刪除與搜尋演算法找出下列25個數的第10小的數：25，50，1，10，31，55，97，87，101，3240，21，75，41，60，34，63，15，86，1147，33，74，81，44。586.設背包限重，有A，B，C三件可分解的物件，其資料如下表：請問應如何將物件放入背包以獲得最大利益？7.若將習題4的圖形視為無向圖，請問此無向圖的最小擴展樹為何？20.6 課後練習(cont.)物物 件件重重

32、 量量利利 益益A550B1060C201405920.7 欲罷不能欲罷不能nBrassard and Bratley,Fundamentals of Algorithmics,Prentice-Hall,1996.nCormen,Leiserson and Rivest,Introduction to Algorithms,MIT Press,2000.nHorowitz,Computer Algorithms in C+,1998.nLee,Tseng,Chang and Tsai,Introduction to Design and Analysis of Algorithms(2nd Ed.),Flag Publishing(旗標),2002。nNeapditan and Naimipour,Foundations of Algorithms,D.C.Heath and Company,1996.60