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

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

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

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

4、 , TD2=N , TD3=N3 n演算法 A 的 最好狀況時間複雜度為 3 n演算法 A 的最差狀況為 N3n演算法 A 的一般狀況為 3+N+N3/3 n稱演算法 A 的時間複雜度為 N3演算法簡介8漸近上限漸近上限 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 = ON2，因為當n 10 時，N2+10N 2N2n稱N2為N2+10N的漸進上限演算法簡介9漸近下限漸近下限 A

5、symptotic Lower Bound 階階次次n假设存在某固定正變數 c 及某非負整數 m 使得對所有 n m，不等式 g n c f n 都成立，則 g n = f n，稱 f n 為 g n 的漸近下限 Examplenn3 = n2，因為當n 1時，n31 n2，所以n2為n3的漸近下限。演算法簡介10真正階次真正階次 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 = ON2 且 N2

6、+10N = N2。演算法簡介11真正階次真正階次cont.n當n足夠大時，2n n3 n2 nlogn n lognf(n)n2nn3n2nlognNlogn121101024840.60205999120.30102999641664162.40823996540.6020599918256512647.22471989680.9030899871665536409625619.26591972161.20411998332429496729632768102448.16479931321.505149978641.84467E+192621444096115.5955183641.806

7、1799741283.40282E+38209715216384269.72287611282.107209972561.15792E+771677721665536616.50943112562.4082399655121.3408E+1541342177282621441387.146225122.709269961演算法簡介12指數函數分析指數函數分析指數函數 Exponential Functionn例如：fn = cpn，其中c為常數，pn為n的多項式函數 Polynomial Function 如n，n2 + 10，log2n，nlog2n nExample:2n、3n、4logn

8、等函數n函數值上升速度相當快時間複雜度為指數函數階次的演算法在資料量足時間複雜度為指數函數階次的演算法在資料量足夠多時需要相當長的時間才能解得答案夠多時需要相當長的時間才能解得答案演算法簡介13多項式時間演算法多項式時間演算法 Polynomial-Time Algorithmn時間複雜度是Opn的演算法，其中pn為n的多項式函數電腦上可解電腦上可解Tractable的問題的問題n能用多項式時間演算法解得答案的問題，即能用電腦在合理時間內求得答案n例如：排序及搜尋等問題演算法簡介14排序法及搜尋法的時間複雜度排序法及搜尋法的時間複雜度 時間複雜度演算法最好狀況最差狀況插入排序O (n)O (n

9、2)氣泡排序O (n)O (n2)謝耳排序O (n)O (n2)兩兩合併排序O (n)O (nlog2n)循序搜尋O (1)O (n)二分搜尋O (1)O (log2n)演算法簡介15最正确演算法最正确演算法 Optimal Algorithmn假设可解問題P的演算法A的時間複雜度為t，而解問題P的演算法最少需要t時間，則稱演算法A是解問題P的最正确演算法最正确演算法 n例如：兩兩合併排序法是最正确排序演算法n排序n個數的問題最少需要Onlog2n時間n兩兩合併排序法的時間複雜度是Onlog2n演算法簡介16難解問題難解問題 Intractable Problemn假设問題P無法以多項式時間演

10、算法解得答案，則問題P無法於電腦上在合理時間內求得答案，稱問題P為難解問題，或NP-Complete問題Examplen旅行推銷員問題 Travelling Salesman Problemn圖形塗色問題 Graph-Coloring Problemn裝箱問題 Bin-Packing Problem演算法簡介1720.2 個別擊破策略個別擊破策略Divide-and-Conquer Methodn將原來的問題P分解成2個或多個子問題n待個別解決這些子問題後再經由合併 merge 處理整理出原來問題的答案n因為分割後的子問題是資料量較小的問題P，因此解子問題時又可遞迴應用上述的方法經由分割及合併

11、的過程得到解答nExample:二分搜尋法，兩兩合併排序法演算法簡介18兩兩合併排序法兩兩合併排序法n一開始就將資料分割成兩部份處理，然後再遞迴細分各資料直至不能細分為止n接著就兩兩合併成排序的序列，渐渐的將分割的資料合併成排序的序列，最後得到所有資料的排序結果1062717324556106271732455610627173245561062717324556610172743256561017274532564561017273256分割分割分割分割分割分割合併合併合併合併合併合併演算法簡介19二分搜尋法二分搜尋法 n假設陣列D中依序放有4, 3, 5, 2, 6, 7, 1等七個整數，

12、目標是將這些數依小到大順序排序n首先觀察第一個數4在最後排序好的序列中應是第四位即應放在D4n假如能將不大於4的數放在D1至D3中而不小於4的數放在D5至D7中則只要再分別排序好D1至D3的數及D5至D7內的數那原來排序問題就解決了演算法簡介20二分搜尋法二分搜尋法cont.方法n令i=2j =7n從Di開始向右找到第一個不小於D1的數以i記錄其陣列的索引n從Dj開始向左找到第一個不大於D1的數以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 UN

13、TIL D(J) = K13 IF I J THEN14 K = D(I)15 D(I) = D(J)16 D(J) = K17 ELSE18 EXIT DO19 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 SUB演算法簡介24快速排序法快速排序法cont.快速排序法n最差時間複雜度為On2 ，其中n為資料個數 n一般狀況時間複雜度為Onlog2n個別擊破策略常用於計算幾何個別擊破策略常用於計算幾何 Computational Geometry 的應用問

14、題的應用問題演算法簡介2520.3 貪婪策略貪婪策略Greedy Method n每次的決策都是朝向目前“最好的方向前進n櫃檯服務問題n某一個銀行出納櫃檯要服務n位顧客，銀行的目標是希望顧客在櫃檯等待的平均時間要最少n解決之道是每次都從尚未服務的顧客中，選擇需要服務時間最短的顧客來服務，如此就可達到預期目標演算法簡介26貪婪策略貪婪策略-實例說明實例說明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

15、 + 4 + 5 / 5 = 7 顧顧客客服服務務時時間間A5B1C4D2E3演算法簡介27背包問題背包問題 Knapsack Problem n假設有多個可分解的物件和一只限重W的背包n每件物件有其重量及其被選取放入背包內的利益n請問要如何將物件放進背包內而使得獲得的利益最大n解決的方法：n是每次在限重的情形下，選取尚未放入的物件中擁有最大的利益與重量的比值之物件放入背包內。演算法簡介28背包問題背包問題-實例說明實例說明n設背包限重100，有A，B，C，D，E共五個物件，其資料如表所示物物件件重重量量利利益益利利益益/重重量量A10202.0B20301.5C30662.2D40401.0

16、E50601.2演算法簡介29背包問題背包問題-實例說明實例說明cont.解法n依利益/重量由大至小順序放入物件，即C, A, B, E, D順序考慮物物件件個個數數累累計計利利益益累累計計重重量量C16630A18640B111660E0.8164100演算法簡介30最小擴展樹最小擴展樹 Minimum Spanning Tree右圖n由頂點 Vertex 及邊 Edge 構成n每一邊都連接兩頂點，可指定其加權Weight ，分有向和無向兩種n圓圈代表頂點n連接兩頂點的線為邊n每個邊都有非負的加權 n例如頂點V3與頂點V5間的邊之加權為5 31456872V2V3V1V4V5演算法簡介31最

17、小擴展樹最小擴展樹cont.n無向圖 Undirected Graph：均是無方向邊的圖形。n無向圖的路徑 Path：由頂點構成的序列，其中序列裏每個頂點與其後一個頂點之間必有邊相連n例如V1, V5, V2是一條從頂點V1到頂點V2的路徑。n聯通圖 Connected Graph：任兩頂點都存在一條路徑的無向圖n例如右圖是聯通圖31456872V2V3V1V4V5演算法簡介32最小擴展樹最小擴展樹cont.n迴圈 Cycle：從某頂點出發回到該頂點的路徑 n例如V1, V5, V2, V1路徑就是迴圈n無迴圈圖 Acyclic Graph：沒有迴圈的圖形n樹 Tree：聯通的無迴圈圖n圖形G

18、=V, E， V是頂點所成的集合， E是邊所成的集合31456872V2V3V1V4V5演算法簡介33最小擴展樹最小擴展樹cont.n圖形G=V, E的擴展樹T=V, E是包括所有G的頂點的樹，其中E是E的子集合。n例如圖a及b都是右上圖的擴展樹31456872V2V3V1V4V53157V2V3V1V4V53162V2V3V1V4V5(a)(b)演算法簡介34最小擴展樹最小擴展樹cont.n擴展樹T=V, E的加權：集合E中所有的邊的加權的總和n例如圖a的擴展樹加權為1+3+5+7=16，而圖b 的擴展樹加權為1+2+3+6=12。n最小擴展樹問題：求出給定的聯通且加權的無向圖之最小擴展樹n

19、圖形G的最小擴展樹就是擁有最小加權的擴展樹n如圖b的擴展樹是右上圖的最小擴展樹3157V2V3V1V4V53162V2V3V1V4V5(a)(b)31456872V2V3V1V4V5演算法簡介35Kruskal演算法演算法nKruskal演算法：依據邊的加權由小到大的順序考慮該邊是否為最小擴展樹的邊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的

20、擴展樹，則重複步驟3；否則，圖形T是圖形G的最小擴展樹，結束演算法執行。演算法簡介36Kruskal演算法實例說明演算法實例說明31456872V2V3V1V4V5演算法簡介37最短路徑問題最短路徑問題 Shortest Path Problemn下圖是S、A、B、T四個地點的交通路線，各路線分別標上距離n令Da,b表示從a到b的最短路徑長度n可知DS,T=DS,A+DA,B+DB,T=10+15+20=45n利用貪婪策略就能得到答案SA104025BT1560203050演算法簡介38最短路徑問題最短路徑問題 cont.n假设要找下圖的DS,T，則DS,T=24+20=44，此結果並不等於D

21、S,A+DA,B+DB,T=45n以動態規劃策略找一般圖形的最短路徑SA104025BT156020305024演算法簡介3920.4 動態規劃動態規劃n個別擊破策略n是遞迴地將問題分成較小的問題後分別求得解答，然後合併這些部份答案成為完好的答案n由上至下 Top-Down 的計算策略nFibonacci函數fn：n f0=0n f1=1n fn = fn-1 + fn-2，n 2演算法簡介40以個別擊破策略計算以個別擊破策略計算f5n過程如下圖所示n其中f3f2f1f0被重複計算許屡次n假如能先依序將f0f1f2f3f4的結果計算出來，就可防止重複計算，增進計算速度。f(5)f(4)f(2)

22、f(3)f(2)f(1)f(1)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)演算法簡介41以個別擊破策略計算以個別擊破策略計算f5cont.n以陣列FIB儲存Fibonacci函數利用下面的方法計算fn： FIB0=0 FIB1=1 FOR I = 2 TO n FIBI = FIBI-1 + FIBI-2 NEXT I演算法簡介42動態規劃動態規劃 Dynamic Programming策略策略n將問題分成小問題然後直接解小問題將結果儲存起來以備之後使用n由下至上 Bottom-Up 計算策略演算法簡介43二項式係數二項式係數 Binomial CoefficientnB

23、n,k=n!/k!n-k!n當nk的值不小時難計算n!及k!n計算速度慢nBn,k = Bn-1,k-1+Bn-1,kif 0 k n 1if k=0 or k=nn以動態規劃策略計算之演算法簡介44二項式係數二項式係數cont.以動態規劃策略計算Bn,kn令陣列BI是一個二維陣列有n+1個列編號從0至nk+1個欄編號從0到kn將Bn,k的值儲存於BIn,k內 FOR I = 0 TO n FOR J = 0 TO mini,k IF J = 0 OR J = I THEN BII, J =1 ELSE BII, J=BII-1,J-1+BII-1,J END IF NEXT J NEXT I

24、 演算法簡介45有向圖的最短路徑問題有向圖的最短路徑問題 Shortest Path Problem n找出在有向及非負加權的圖形上任兩頂點的最短路徑。n圓圈代表頂點n連接兩頂點的線稱為邊n每個邊都有方向也有對應的非負的加權 n有向圖的路徑是一個頂點序列，其中序列裏每個頂點到其後一個頂點的邊一定存在n例如V1, V3, V2就是一條從頂點V1至頂點V2的路徑。n路徑的長度為路徑上所有的邊的加權的和n例如路徑V1, V3, V2的長度為6+4=10。2V1V2741V3V45631演算法簡介46有向圖的最短路徑問題有向圖的最短路徑問題cont.n假設圖形有n個頂點分別是V1, , Vn。n令dk

25、i,j表示只有經過集合V1, V2, , Vk中某頂點的Vi到Vj的最短路徑長度n令d0i,j為Vi到Vj的邊的加權n經過集合V1, ,Vk中某些頂點的Vi到Vj最短路徑可能不經過Vk也可能經過Vkn假如不經過Vk則dki,j = dk-1i,j；n假如經過Vk，則dki,j = dk-1i,k+dk-1k,jndki,j=mindk-1i,j, dk-1i,k+dk-1k,j演算法簡介47有向圖的最短路徑問題有向圖的最短路徑問題cont.d01234d11234101621016221021073354035407437043470d21234d31234101621016221073210

26、7335407354074347043470d41234101622107335407434702V1V2741V3V45631演算法簡介48有向圖的最短路徑問題有向圖的最短路徑問題cont.n假設Vi到Vj的最短路徑經過Vk則Vi到Vk的路徑也是最短的路徑而Vk到Vj的路徑也是最短的。n例如由V2到V4的最短路徑為V2, V1, V4而路徑V2, V1也是V2到V1的最短路徑而路徑V1, V4也是V1到V4的最短路徑n最正确解包含其組成份子的最正确解之特性稱為最正确化原則最正确化原則 Principle of Optimalityn假如最正确化問題能應用此最正确化原則則可以用動態規劃策略設計

27、遞迴運算式來求得最正确解演算法簡介4920.5 刪除與搜尋策略刪除與搜尋策略Prune-and-Search Method n包含屡次的處理，每次的處理都會將輸入資料刪除固定的百分比，並運用同樣的方法遞迴地以刪除後的資料當作輸入資料重新解問題，經過假设干次處理後，資料量將可縮小到能用固定常數的時間解得答案nExample：二元搜尋法的每個步驟能去除一半的資料，是典型的刪除與搜尋演算法演算法簡介50刪除與搜尋策略刪除與搜尋策略cont.找出 n 個數的第 k 小的數n直接的解法：將這 n 個數由小到大排好後，然後就能依序找出第 k 小的數nOnlog2n時間。n刪除與搜尋策略：On時間演算法簡介

28、51刪除與搜尋策略刪除與搜尋策略-範例範例假設 n 為 5 的倍數n步驟 1 ： 將此 n 個數，分成 n/5 個數堆,每堆 5 個數。n步驟 2 ：分別將各數堆排序。n步驟 3 ：令 P 為數堆中間值的中間值。n步驟 4 ：令 S1 為小於 P 的數所成的集合，S2為等於 P 的數所成的集合，S3為大於 P 的數所成的集合。n步驟 5 ：假设 S1 的元素個數大於或等於 K，則丟棄 S2及S3，並繼續利用本演算法找尋 S1 中的第 K 小的數。否則，假如S1 與 S2 的元素個數和大於或等於 K ，則 P 為第 K 小數;否則，令 K = K - |S1| - |S2| ，丟棄 S1及 S2

29、，並繼續利用本演算法找尋 S3 中的第K小的數演算法簡介52刪除與搜尋策略刪除與搜尋策略-範例範例cont.n假設 n =25，經過步驟 1 分成 25/5 =5 個數堆後的資料32120112513481511419610716923121722182425圖20.10演算法簡介53刪除與搜尋策略刪除與搜尋策略-範例範例cont.n各數堆排序後，此時各數堆的中間值分別為 11 , 8 , 10 , 12 , 22 ， 而 11 是這些數的中間值。23112021458131516101419791216231718222425圖20.11演算法簡介54刪除與搜尋策略刪除與搜尋策略-範例範例cont.n將數堆位置調整後，左上角的矩形部份為 S1 和 S2，而右下角的矩形部份為 S2 和 S323112021458131516101419791216231718222425圖20.12S2S3最少n/4個數S1S2最少n/4個數演算法簡介55刪除與搜尋策略刪除與搜尋策略-範例範例cont.n步驟5可能丟棄S2及S3，或丟棄S1及S2，n被丟棄的資料至少為n/4個數n每執行一次此演算法，資料將只剩下n-n/4 = 3n/4個數。n令Tn表示此演