【文档说明】[计算机]演算法简介课件.ppt，共(60)页，583.520 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77134.html

以下为本文档部分文字说明：

演算法簡介1第二十章演算法簡介知己知彼，百戰不貽－孫子ij+++++----1234演算法簡介2內容前言20.1演算法分析20.2個別擊破策略20.3貪婪策略20.4動態規劃20.5刪除與搜尋策略20.6課

後習題20.7欲罷不能演算法簡介3前言演算法(Algorithm)電腦上解決問題的方法包括明確的輸出入資料和詳細且有限的執行步驟了解每個演算法在不同狀況下所花的時間，而從中挑選適合的演算法以迅速得到答案演算

法設計策略演算法簡介420.1演算法分析在電腦上解決問題的基本架構演算法以程式描述後在電腦上執行，資料輸入至程式後，經過程式對資料的運算，最後產生解答資料演算法（程式）圖20.1解答演算法簡介5時間複雜度

(TimeComplexity)假設演算法A能解問題P問題P的輸入資料量為N假設資料量為N的資料樣本(DataInstance)有D1,D2,...,Di,...,Dm共m種令T(Di)表示當輸入資料為Di時演算法A要執行的運算或步驟的總次數演算法A的最好狀況時間複雜度

(Best-CaseTimeComplexity)T(Di)(1im)中最小的值，即min1im{T(Di)}演算法簡介6時間複雜度(cont.)演算法A的最差狀況時間複雜度(Worst-CaseTimeComplexity)T(Di)(1im)中最大者，即max1

im{T(Di)}演算法A的一般狀況時間複雜度(Average-CaseTimeComplexity)T(Di)(1im)的平均值或期望值(在某機率假設下)說“演算法A的時間複雜度為C”就是指其最差狀況時間複雜度為C演算法簡介7時間複雜度(cont.)範例

若問題P之輸入資料量為N的樣本有D1,D2,D3三種，且T(D1)=3,T(D2)=N,T(D3)=N3演算法A的最好狀況時間複雜度為3演算法A的最差狀況為N3演算法A的一般狀況為(3+N+N3)/3稱演算法

A的時間複雜度為N3演算法簡介8漸近上限(AsymptoticUpperBound)O階次如果存在某固定正實數c及某個非負整數m使得對所有的nm，不等式g(n)cf(n)都成立，則g(n)=O(f(n))，稱f(n)為g(n)的漸近上限Exam

ple:N2+10N=O(N2)，因為當n10時，N2+10N2N2稱N2為N2+10N的漸進上限演算法簡介9漸近下限(AsymptoticLowerBound)階次若存在某固定正變數c及某非負整數m使得對所有nm，不等式g(n)cf(n)都成立，則g(n)=(f(n))，稱

f(n)為g(n)的漸近下限Examplen3=(n2)，因為當n1時，n31n2，所以n2為n3的漸近下限。演算法簡介10真正階次(ExactOrder)若存在某固定正變數c及某非負整數m使得對所有nm，不等式g(n)cf(n)都

成立，則g(n)=(f(n))，稱f(n)為g(n)的漸近下限ExampleN2+10N=(N2)，因為N2+10N=O(N2)且N2+10N=(N2)。演算法簡介11真正階次(cont.)當n足夠大時，2n>n3>n2>nlogn>n>lognf(n)n2nn3

n2nlognNlogn121101024840.60205999120.30102999641664162.40823996540.6020599918256512647.22471989680.903089987

1665536409625619.26591972161.20411998332429496729632768102448.16479931321.505149978641.84467E+192621444096115.5955183641.8

061799741283.40282E+38209715216384269.72287611282.107209972561.15792E+771677721665536616.50943112562.408239

9655121.3408E+1541342177282621441387.146225122.709269961演算法簡介12指數函數分析指數函數(ExponentialFunction)例如：f(n)=cp(n)，其中c為常數，p(n)為n的多項式函數

(PolynomialFunction)(如n，n2+10，log2n，nlog2n)Example:2n、3n、4logn等函數函數值上升速度相當快時間複雜度為指數函數階次的演算法在資料量足夠多時需要相當長的時間才能解得答案演算法簡介13多項式時間演算法(Polynomia

l-TimeAlgorithm)時間複雜度是O(p(n))的演算法，其中p(n)為n的多項式函數電腦上可解（Tractable）的問題能用多項式時間演算法解得答案的問題，即能用電腦在合理時間內求得答案例如：排序及搜尋等問題演算法

簡介14排序法及搜尋法的時間複雜度時間複雜度演算法最好狀況最差狀況插入排序O(n)O(n2)氣泡排序O(n)O(n2)謝耳排序O(n)O(n2)兩兩合併排序O(n)O(nlog2n)循序搜尋O(1)O(n)二分搜尋O(1)O(l

og2n)演算法簡介15最佳演算法(OptimalAlgorithm)若可解問題P的演算法A的時間複雜度為t，而解問題P的演算法最少需要t時間，則稱演算法A是解問題P的最佳演算法例如：兩兩合併排序法是最佳排序演算法排序n個數的問題最少需要O(nlog2

n)時間兩兩合併排序法的時間複雜度是O(nlog2n)演算法簡介16難解問題(IntractableProblem)若問題P無法以多項式時間演算法解得答案，則問題P無法於電腦上在合理時間內求得答案，稱問題P為難解問題，

或NP-Complete問題Example旅行推銷員問題(TravellingSalesmanProblem)圖形塗色問題(Graph-ColoringProblem)裝箱問題(Bin-PackingProblem)演算法簡介1

720.2個別擊破策略(Divide-and-ConquerMethod)將原來的問題P分解成2個或多個子問題待個別解決這些子問題後再經由合併(merge)處理﹐整理出原來問題的答案﹐因為分割後的子問題是資料量較小的問題P，因此解子問題時又可遞迴應用上述的方法﹐經由分割及合併

的過程得到解答Example:二分搜尋法，兩兩合併排序法演算法簡介18兩兩合併排序法一開始就將資料分割成兩部份處理，然後再遞迴細分各資料直至不能細分為止接著就兩兩合併成排序的序列，慢慢的將分割的資料合併成排序的序列，最後得到所有

資料的排序結果1062717324556106271732455610627173245561062717324556610172743256561017274532564561017273256分割分割分

割合併合併合併演算法簡介19二分搜尋法假設陣列D中依序放有4,3,5,2,6,7,1等七個整數，目標是將這些數依小到大順序排序首先觀察第一個數4在最後排序好的序列中應是第四位﹐即應放在D(4)如果能將不大於4的數放在D(1)至D(3)中﹐而不小

於4的數放在D(5)至D(7)中﹐則只要再分別排序好D(1)至D(3)的數及D(5)至D(7)內的數﹐那原來排序問題就解決了演算法簡介20二分搜尋法(cont.)方法令i=2﹐j=7從D(i)開始向右找到第一個不小

於D(1)的數﹐以i記錄其陣列的索引從D(j)開始向左找到第一個不大於D(1)的數﹐以j記錄其陣列索引若i<j，則交換D(i)與D(j)的內容，並繼續前述的左右搜尋；若ij，則交換D(1)與D(j

)的內容，並停止搜尋演算法簡介21二分搜尋法(cont.)確定4的位置將不大於4的資料放其左方將不小於4的資料放其右方D(2)D(1)D(3)D(4)D(5)D(6)D(7)3452671i=2j=7D(2)D(1)D(3)D(4)D(5)D(6)D

(7)3452671i=3j=7左右搜尋D(2)D(1)D(3)D(4)D(5)D(6)D(7)3412675i=3j=7交換D(7)與D(3)i=5j=4D(2)D(1)D(3)D(4)D(5)D(6)D(7)3412675左右搜尋D(2

)D(1)D(3)D(4)D(5)D(6)D(7)3214675交換D(1)與D(4)演算法簡介22快速排序法(QuickSort)原來的排序問題可細分為排序D(1)至D(3)的數及排序D(5)至D(7)的數的兩個子問題待解決子問題題後，可依

序將答案組合起來，就是原來的答案。而分割後的子問題仍是排序問題可再利用前一段敘述的方法排序之345267132146752134567分割2135674213567分割分割4合併合併合併D(2)D(1)

D(3)D(4)D(5)D(6)D(7)演算法簡介23快速排序法-程式QSORT副程式以快速排序法對陣列D(M)至D(N)的元素排序1SUBQSORT(M,N)2IFM>NTHEN3I=M4J=N+15K=D(M)6DO7DO8I=I+19LOOPUNTILD(

I)>=K10DO11J=J-112LOOPUNTILD(J)<=K13IFI<JTHEN14K=D(I)15D(I)=D(J)16D(J)=K17ELSE18EXITDO19ENDIF20LOOP21K=D(M)22D(M)=D(J)23D(J)=K24QSORT(

M,J-1)25QSORT(J+1,N)26ENDIF27ENDSUB演算法簡介24快速排序法(cont.)快速排序法最差時間複雜度為O(n2)，其中n為資料個數一般狀況時間複雜度為O(nlog2n)個別擊破策略常用於計算幾何(Computa

tionalGeometry)的應用問題演算法簡介2520.3貪婪策略(GreedyMethod)每次的決策都是朝向目前“最好”的方向前進櫃檯服務問題某一個銀行出納櫃檯要服務n位顧客，銀行的目標是希望顧客在櫃檯等待的平均時間要最少解決之道是每次都從尚未服

務的顧客中，選擇需要服務時間最短的顧客來服務，如此就可達到預期目標演算法簡介26貪婪策略-實例說明假設有5個顧客A，B，C，D，E幾乎同時到達銀行櫃檯，其所需服務時間如表所示銀行櫃檯將依序服務B，D，E，C，A顧客在櫃檯等待的平均

時間為[1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)]/5=7顧客服務時間A5B1C4D2E3演算法簡介27背包問題(KnapsackProblem)假設有多個可分解的

物件和一只限重W的背包每件物件有其重量及其被選取放入背包內的利益請問要如何將物件放進背包內而使得獲得的利益最大解決的方法：是每次在限重的情形下，選取尚未放入的物件中擁有最大的利益與重量的比值之物件放入背包內。演算法簡介28背包問題-實例說明

設背包限重100，有A，B，C，D，E共五個物件，其資料如表所示物件重量利益利益/重量A10202.0B20301.5C30662.2D40401.0E50601.2演算法簡介29背包問題-實例說明(cont.)解法依利益/重量由大至小順序放入物件，即C,A,B,E,D順序考慮物件個數累計

利益累計重量C16630A18640B111660E0.8164100演算法簡介30最小擴展樹(MinimumSpanningTree)右圖由頂點(Vertex)及邊(Edge)構成每一邊都連接兩頂

點，可指定其加權(Weight)，分有向和無向兩種圓圈代表頂點連接兩頂點的線為邊每個邊都有非負的加權例如頂點V3與頂點V5間的邊之加權為531456872V2V3V1V4V5演算法簡介31最小擴展樹(cont.)無向圖(UndirectedGr

aph)：均是無方向邊的圖形。無向圖的路徑(Path)：由頂點構成的序列，其中序列裏每個頂點與其後一個頂點之間必有邊相連例如[V1,V5,V2]是一條從頂點V1到頂點V2的路徑。聯通圖(ConnectedG

raph)：任兩頂點都存在一條路徑的無向圖例如右圖是聯通圖31456872V2V3V1V4V5演算法簡介32最小擴展樹(cont.)迴圈(Cycle)：從某頂點出發回到該頂點的路徑例如[V1,V5,V2,V1]路徑就是迴圈無迴圈圖(AcyclicGr

aph)：沒有迴圈的圖形樹(Tree)：聯通的無迴圈圖圖形G=(V,E)，V是頂點所成的集合，E是邊所成的集合31456872V2V3V1V4V5演算法簡介33最小擴展樹(cont.)圖形G=(V,E)的擴展樹T=(V,E’)

是包括所有G的頂點的樹，其中E’是E的子集合。例如圖(a)及(b)都是右上圖的擴展樹31456872V2V3V1V4V53157V2V3V1V4V53162V2V3V1V4V5(a)(b)演算法簡介34最小擴展樹(cont.)擴展樹T=(V,E’)的加權：集合E’中所有的邊的加權的總和

例如圖(a)的擴展樹加權為1+3+5+7=16，而圖(b)的擴展樹加權為1+2+3+6=12。最小擴展樹問題：求出給定的聯通且加權的無向圖之最小擴展樹圖形G的最小擴展樹就是擁有最小加權的擴展樹如圖(b)的擴展樹是右上圖的最小擴展樹315

7V2V3V1V4V53162V2V3V1V4V5(a)(b)31456872V2V3V1V4V5演算法簡介35Kruskal演算法Kruskal演算法：依據邊的加權由小到大的順序考慮該邊是否為最小擴展樹的邊步驟1：將圖形G=(V,E)所有的邊依其加權由小到大排好，依序

為e1,e2,e3,…,em。步驟2：建立圖形T=(V,E’)，其中E’=Φ。設i=1。步驟3：若ei加入圖形T中不產生迴圈，則將ei加入圖形T，即E’=E’{ei}；否則，i=i+1。步驟4：若

圖形T不是圖形G的擴展樹，則重複步驟3；否則，圖形T是圖形G的最小擴展樹，結束演算法執行。演算法簡介36Kruskal演算法實例說明31456872V2V3V1V4V5演算法簡介37最短路徑問題(ShortestPathProblem)下圖是S、A、B、T四個地點的交通路線，各路線分別標

上距離令D(a,b)表示從a到b的最短路徑長度可知D(S,T)=D(S,A)+D(A,B)+D(B,T)=10+15+20=45利用貪婪策略就能得到答案SA104025BT1560203050演算法簡介38最短路徑問題(cont.)若要找下圖的D(S,T)，則D(S,T)=24+20=44

，此結果並不等於D(S,A)+D(A,B)+D(B,T)=45以動態規劃策略找一般圖形的最短路徑SA104025BT156020305024演算法簡介3920.4動態規劃個別擊破策略是遞迴地將問題分成較小的問題後分別求得解答，然後合併這些

部份答案成為完整的答案由上至下(Top-Down)的計算策略Fibonacci函數f(n)：f(0)=0f(1)=1f(n)=f(n-1)+f(n-2)，n2演算法簡介40以個別擊破策略計算f(5)過程如下圖所示其中f(3)﹐f

(2)﹐f(1)﹐f(0)被重複計算許多次如果能先依序將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)演算法簡介41以個別擊破策略計算f(5)(cont.)以陣列FIB儲存Fibonacci函數﹐利用下面的方法計算f(n)：FIB(0)=0FIB(1)=1FORI=2TOnFIB(I)=FIB(I-1)+FIB(I-2)NEXTI演算法簡介4

2動態規劃(DynamicProgramming)策略將問題分成小問題﹐然後直接解小問題﹐將結果儲存起來以備之後使用由下至上(Bottom-Up)計算策略演算法簡介43二項式係數(BinomialCoefficient)B(n,k)=n!/(k!(n-k)!)當n﹐k

的值不小時﹐難計算n!及k!計算速度慢B(n,k)=B(n-1,k-1)+B(n-1,k)if0<k<n1ifk=0ork=n以動態規劃策略計算之演算法簡介44二項式係數(cont.)以動態規劃策略計算B(n,

k)令陣列BI是一個二維陣列﹐有n+1個列(編號從0至n)﹐k+1個欄(編號從0到k)將B(n,k)的值儲存於BI(n,k)內FORI=0TOnFORJ=0TOmin{i,k}IFJ=0ORJ=ITHENBI(I,J)=1ELSEBI(I,J)=BI(I-1,J-1)+BI(I-1,

J)ENDIFNEXTJNEXTI演算法簡介45有向圖的最短路徑問題(ShortestPathProblem)找出在有向及非負加權的圖形上任兩頂點的最短路徑。圓圈代表頂點連接兩頂點的線稱為邊每個邊都有方向也有對應的非負的加權有向圖的路徑是一個頂點序列，其中序列裏每個頂點到其後一個

頂點的邊一定存在例如[V1,V3,V2]就是一條從頂點V1至頂點V2的路徑。路徑的長度為路徑上所有的邊的加權的和例如路徑[V1,V3,V2]的長度為6+4=10。2V1V2741V3V45631演算法簡介46有向圖的最短路徑問題(cont.)假設圖形有n

個頂點﹐分別是V1,…,Vn。令dk(i,j)表示只有經過集合{V1,V2,…,Vk}中某頂點的Vi到Vj的最短路徑長度﹐令d0(i,j)為Vi到Vj的邊的加權經過集合{V1,…,Vk}中某些頂點的

Vi到Vj最短路徑可能不經過Vk﹐也可能經過Vk如果不經過Vk﹐則dk(i,j)=dk-1(i,j)；如果經過Vk，則dk(i,j)=dk-1(i,k)+dk-1(k,j)dk(i,j)=min{dk-1(i,j),dk-1(i,k)+dk-1

(k,j)}演算法簡介47有向圖的最短路徑問題(cont.)d01234d112341016210162210∞∞210733540∞3540743∞7043470d21234d31234101621016221073210733540

7354074347043470d41234101622107335407434702V1V2741V3V45631演算法簡介48有向圖的最短路徑問題(cont.)假設Vi到Vj的最短路徑經過Vk﹐則Vi到Vk的路徑也是最短的路徑﹐而Vk到Vj的路徑也是最短的。例如﹐由V

2到V4的最短路徑為[V2,V1,V4]﹐而路徑[V2,V1]也是V2到V1的最短路徑﹐而路徑[V1,V4]也是V1到V4的最短路徑最佳解包含其組成份子的最佳解之特性﹐稱為最佳化原則(Principleo

fOptimality)如果最佳化問題能應用此最佳化原則﹐則可以用動態規劃策略設計遞迴運算式來求得最佳解演算法簡介4920.5刪除與搜尋策略(Prune-and-SearchMethod)包含多次的處理，每次的處理都會將輸入

資料刪除固定的百分比，並運用同樣的方法遞迴地以刪除後的資料當作輸入資料重新解問題，經過若干次處理後，資料量將可縮小到能用固定常數的時間解得答案Example：二元搜尋法的每個步驟能去除一半的資料，是典型的刪除與搜尋演算

法演算法簡介50刪除與搜尋策略(cont.)找出n個數的第k小的數直接的解法：將這n個數由小到大排好後，然後就能依序找出第k小的數O(nlog2n)時間。刪除與搜尋策略：O(n)時間演算法簡介51刪除與

搜尋策略-範例假設n為5的倍數步驟1：將此n個數，分成n/5個數堆,每堆5個數。步驟2：分別將各數堆排序。步驟3：令P為數堆中間值的中間值。步驟4：令S1為小於P的數所成的集合，S2為等於P的數所成的集合，S3為大於P的數所成的集合。步驟5：若S1的元素個數大於或等於K，則丟棄

S2及S3，並繼續利用本演算法找尋S1中的第K小的數。否則，如果S1與S2的元素個數和大於或等於K，則P為第K小數;否則，令K’=K-|S1|-|S2|，丟棄S1及S2，並繼續利用本演算法找尋S3中的第K’小的數演算法簡介52刪除與搜尋策略-範例(cont.)假設n=25，經過步驟1分成25

/5=5個數堆後的資料32120112513481511419610716923121722182425圖20.10演算法簡介53刪除與搜尋策略-範例(cont.)各數堆排序後，此時各數堆的中間值分別為11,8,10,12,22，而11是這些數的中間值。231120214581

31516101419791216231718222425圖20.11演算法簡介54刪除與搜尋策略-範例(cont.)將數堆位置調整後，左上角的矩形部份為S1和S2，而右下角的矩形部份為S2和S323112

021458131516101419791216231718222425圖20.12S2S3最少n/4個數S1S2最少n/4個數演算法簡介55刪除與搜尋策略-範例(cont.)步驟5可能丟棄S2及S3，或丟棄S1及S2，被丟棄的資料至少為

n/4個數每執行一次此演算法，資料將只剩下n-(n/4)=3n/4個數。令T(n)表示此演算法在n個數中找第k小的數所需的時間T(n)=T(3n/4)+O(n)步驟1至步驟4需O(n)時間得T(n)=O(n)刪

除與搜尋策略能應用於如雙變數的線性規劃問題、單中心問題等計算幾何問題。演算法簡介5620.6課後練習1.以快速排序法完成下列１0個數的排序：10,21，5，31，42，24，90，50，15，2。2.假設有面額１５元、１０元、５元及１元郵

票。若某郵件需４９元的郵資，為了讓郵票張數最少，請問這些面額的郵票各需幾張？(提示：貪婪策略)3.分別以O、Ω、θ階次表示下列各函數：a)0.001n2+nb)n+log2nc)2n+nlog2n演算法簡介572

0.6課後練習(cont.)4.請以動態規劃演算法找出下圖任兩頂點的最短路徑：V24V352V171V4621演算法簡介5820.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。演算法簡介596.設背包限重３０，有A，B，C三件可分解的物件，其資料如下表：請問應如何將物件放入背包以獲得最大利益？7.若將習題4的圖形

視為無向圖，請問此無向圖的最小擴展樹為何？20.6課後練習(cont.)物件重量利益A550B1060C20140演算法簡介6020.7欲罷不能BrassardandBratley,FundamentalsofAlgorithmics,Prentice-Hall,1

996.Cormen,LeisersonandRivest,IntroductiontoAlgorithms,MITPress,2000.Horowitz,ComputerAlgorithmsinC++,1

998.Lee,Tseng,ChangandTsai,IntroductiontoDesignandAnalysisofAlgorithms(2ndEd.),FlagPublishing(旗標),2002。NeapditanandNaimipour,Foundationsof

Algorithms,D.C.HeathandCompany,1996.