[計(jì)算機(jī)]演算法簡(jiǎn)介ppt課件

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

2、問(wèn)題的根本架構(gòu)在電腦上解決問(wèn)題的根本架構(gòu)n演算法以程式描繪後在電腦上執(zhí)行，資料輸入至程式後，經(jīng)過(guò)程式對(duì)資料的運(yùn)算，最後產(chǎn)生解答資料演算法（程式）圖 20.1解答演算法簡(jiǎn)介5時(shí)間複雜度時(shí)間複雜度 Time Complexityn假設(shè)演算法 A 能解問(wèn)題Pn問(wèn)題P的輸入資料量為Nn假設(shè)資料量為N的資料樣本 Data Instance 有 D1 , D2 , . , Di , . , Dm 共 m 種n令 TDi 表示當(dāng)輸入資料為 Di 時(shí)演算法 A 要執(zhí)行的運(yùn)算或步驟的總次數(shù)n演算法 A 的最好狀況時(shí)間複雜度最好狀況時(shí)間複雜度 Best-Case Time Complexityn TDi1 i m

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

4、 , TD2=N , TD3=N3 n演算法 A 的 最好狀況時(shí)間複雜度為 3 n演算法 A 的最差狀況為 N3n演算法 A 的一般狀況為 3+N+N3/3 n稱演算法 A 的時(shí)間複雜度為 N3演算法簡(jiǎn)介8漸近上限漸近上限 Asymptotic Upper Bound O階階次次n假如存在某固定正實(shí)數(shù) c 及某個(gè)非負(fù)整數(shù) m 使得對(duì)所有的 n m，不等式 g n c f n 都成立，則 g n = O f n，稱 f n 為 g n 的漸近上限 Example: nN2+10N = ON2，因?yàn)楫?dāng)n 10 時(shí)，N2+10N 2N2n稱N2為N2+10N的漸進(jìn)上限演算法簡(jiǎn)介9漸近下限漸近下限 A

5、symptotic Lower Bound 階階次次n假設(shè)存在某固定正變數(shù) c 及某非負(fù)整數(shù) m 使得對(duì)所有 n m，不等式 g n c f n 都成立，則 g n = f n，稱 f n 為 g n 的漸近下限 Examplenn3 = n2，因?yàn)楫?dāng)n 1時(shí)，n31 n2，所以n2為n3的漸近下限。演算法簡(jiǎn)介10真正階次真正階次 Exact Order n假設(shè)存在某固定正變數(shù) c 及某非負(fù)整數(shù) m 使得對(duì)所有 n m，不等式 g n c f n 都成立，則 g n = f n，稱 f n 為 g n 的漸近下限 ExamplenN2+10N = N2，因?yàn)?N2+10N = ON2 且 N2

6、+10N = N2。演算法簡(jiǎn)介11真正階次真正階次cont.n當(dāng)n足夠大時(shí)，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演算法簡(jiǎn)介12指數(shù)函數(shù)分析指數(shù)函數(shù)分析指數(shù)函數(shù) Exponential Functionn例如：fn = cpn，其中c為常數(shù)，pn為n的多項(xiàng)式函數(shù) Polynomial Function 如n，n2 + 10，log2n，nlog2n nExample:2n、3n、4logn

8、等函數(shù)n函數(shù)值上升速度相當(dāng)快時(shí)間複雜度為指數(shù)函數(shù)階次的演算法在資料量足時(shí)間複雜度為指數(shù)函數(shù)階次的演算法在資料量足夠多時(shí)需要相當(dāng)長(zhǎng)的時(shí)間才能解得答案夠多時(shí)需要相當(dāng)長(zhǎng)的時(shí)間才能解得答案演算法簡(jiǎn)介13多項(xiàng)式時(shí)間演算法多項(xiàng)式時(shí)間演算法 Polynomial-Time Algorithmn時(shí)間複雜度是Opn的演算法，其中pn為n的多項(xiàng)式函數(shù)電腦上可解電腦上可解Tractable的問(wèn)題的問(wèn)題n能用多項(xiàng)式時(shí)間演算法解得答案的問(wèn)題，即能用電腦在合理時(shí)間內(nèi)求得答案n例如：排序及搜尋等問(wèn)題演算法簡(jiǎn)介14排序法及搜尋法的時(shí)間複雜度排序法及搜尋法的時(shí)間複雜度 時(shí)間複雜度演算法最好狀況最差狀況插入排序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)演算法簡(jiǎn)介15最正確演算法最正確演算法 Optimal Algorithmn假設(shè)可解問(wèn)題P的演算法A的時(shí)間複雜度為t，而解問(wèn)題P的演算法最少需要t時(shí)間，則稱演算法A是解問(wèn)題P的最正確演算法最正確演算法 n例如：兩兩合併排序法是最正確排序演算法n排序n個(gè)數(shù)的問(wèn)題最少需要Onlog2n時(shí)間n兩兩合併排序法的時(shí)間複雜度是Onlog2n演算法簡(jiǎn)介16難解問(wèn)題難解問(wèn)題 Intractable Problemn假設(shè)問(wèn)題P無(wú)法以多項(xiàng)式時(shí)間演

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

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

12、目標(biāo)是將這些數(shù)依小到大順序排序n首先觀察第一個(gè)數(shù)4在最後排序好的序列中應(yīng)是第四位即應(yīng)放在D4n假如能將不大於4的數(shù)放在D1至D3中而不小於4的數(shù)放在D5至D7中則只要再分別排序好D1至D3的數(shù)及D5至D7內(nèi)的數(shù)那原來(lái)排序問(wèn)題就解決了演算法簡(jiǎn)介20二分搜尋法二分搜尋法cont.方法n令i=2j =7n從Di開(kāi)始向右找到第一個(gè)不小於D1的數(shù)以i記錄其陣列的索引n從Dj開(kāi)始向左找到第一個(gè)不大於D1的數(shù)以j記錄其陣列索引n假設(shè)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演算法簡(jiǎn)介24快速排序法快速排序法cont.快速排序法n最差時(shí)間複雜度為On2 ，其中n為資料個(gè)數(shù) n一般狀況時(shí)間複雜度為Onlog2n個(gè)別擊破策略常用於計(jì)算幾何個(gè)別擊破策略常用於計(jì)算幾何 Computational Geometry 的應(yīng)用問(wèn)

14、題的應(yīng)用問(wèn)題演算法簡(jiǎn)介2520.3 貪婪策略貪婪策略Greedy Method n每次的決策都是朝向目前“最好的方向前進(jìn)n櫃檯服務(wù)問(wèn)題n某一個(gè)銀行出納櫃檯要服務(wù)n位顧客，銀行的目標(biāo)是希望顧客在櫃檯等待的平均時(shí)間要最少n解決之道是每次都從尚未服務(wù)的顧客中，選擇需要服務(wù)時(shí)間最短的顧客來(lái)服務(wù)，如此就可達(dá)到預(yù)期目標(biāo)演算法簡(jiǎn)介26貪婪策略貪婪策略-實(shí)例說(shuō)明實(shí)例說(shuō)明n假設(shè)有5個(gè)顧客A，B，C，D，E幾乎同時(shí)到達(dá)銀行櫃檯，其所需服務(wù)時(shí)間如表所示n銀行櫃檯將依序服務(wù)B，D，E，C，An顧客在櫃檯等待的平均時(shí)間為 1 + 1 + 2 + 1 + 2 + 3 + 1 + 2 + 3 + 4 + 1 + 2 + 3

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

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

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

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

19、圖形G的最小擴(kuò)展樹(shù)就是擁有最小加權(quán)的擴(kuò)展樹(shù)n如圖b的擴(kuò)展樹(shù)是右上圖的最小擴(kuò)展樹(shù)3157V2V3V1V4V53162V2V3V1V4V5(a)(b)31456872V2V3V1V4V5演算法簡(jiǎn)介35Kruskal演算法演算法nKruskal演算法：依據(jù)邊的加權(quán)由小到大的順序考慮該邊是否為最小擴(kuò)展樹(shù)的邊n步驟1：將圖形G=V, E所有的邊依其加權(quán)由小到大排好，依序?yàn)閑1, e2, e3, , em。n步驟2：建立圖形T=V, E，其中 E = 。設(shè)i = 1。n步驟3：假設(shè)ei參加圖形T中不產(chǎn)生迴圈，則將ei參加圖形T，即E= E ei ；否則，i = i + 1。n步驟4：假設(shè)圖形T不是圖形G的

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

21、S,A+DA,B+DB,T=45n以動(dòng)態(tài)規(guī)劃策略找一般圖形的最短路徑SA104025BT156020305024演算法簡(jiǎn)介3920.4 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃n個(gè)別擊破策略n是遞迴地將問(wèn)題分成較小的問(wèn)題後分別求得解答，然後合併這些部份答案成為完好的答案n由上至下 Top-Down 的計(jì)算策略nFibonacci函數(shù)fn：n f0=0n f1=1n fn = fn-1 + fn-2，n 2演算法簡(jiǎn)介40以個(gè)別擊破策略計(jì)算以個(gè)別擊破策略計(jì)算f5n過(guò)程如下圖所示n其中f3f2f1f0被重複計(jì)算許屢次n假如能先依序?qū)0f1f2f3f4的結(jié)果計(jì)算出來(lái)，就可防止重複計(jì)算，增進(jìn)計(jì)算速度。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)演算法簡(jiǎn)介41以個(gè)別擊破策略計(jì)算以個(gè)別擊破策略計(jì)算f5cont.n以陣列FIB儲(chǔ)存Fibonacci函數(shù)利用下面的方法計(jì)算fn： FIB0=0 FIB1=1 FOR I = 2 TO n FIBI = FIBI-1 + FIBI-2 NEXT I演算法簡(jiǎn)介42動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 Dynamic Programming策略策略n將問(wèn)題分成小問(wèn)題然後直接解小問(wèn)題將結(jié)果儲(chǔ)存起來(lái)以備之後使用n由下至上 Bottom-Up 計(jì)算策略演算法簡(jiǎn)介43二項(xiàng)式係數(shù)二項(xiàng)式係數(shù) Binomial CoefficientnB

23、n,k=n!/k!n-k!n當(dāng)nk的值不小時(shí)難計(jì)算n!及k!n計(jì)算速度慢nBn,k = Bn-1,k-1+Bn-1,kif 0 k n 1if k=0 or k=nn以動(dòng)態(tài)規(guī)劃策略計(jì)算之演算法簡(jiǎn)介44二項(xiàng)式係數(shù)二項(xiàng)式係數(shù)cont.以動(dòng)態(tài)規(guī)劃策略計(jì)算Bn,kn令陣列BI是一個(gè)二維陣列有n+1個(gè)列編號(hào)從0至nk+1個(gè)欄編號(hào)從0到kn將Bn,k的值儲(chǔ)存於BIn,k內(nèi) 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、 演算法簡(jiǎn)介45有向圖的最短路徑問(wèn)題有向圖的最短路徑問(wèn)題 Shortest Path Problem n找出在有向及非負(fù)加權(quán)的圖形上任兩頂點(diǎn)的最短路徑。n圓圈代表頂點(diǎn)n連接兩頂點(diǎn)的線稱為邊n每個(gè)邊都有方向也有對(duì)應(yīng)的非負(fù)的加權(quán) n有向圖的路徑是一個(gè)頂點(diǎn)序列，其中序列裏每個(gè)頂點(diǎn)到其後一個(gè)頂點(diǎn)的邊一定存在n例如V1, V3, V2就是一條從頂點(diǎn)V1至頂點(diǎn)V2的路徑。n路徑的長(zhǎng)度為路徑上所有的邊的加權(quán)的和n例如路徑V1, V3, V2的長(zhǎng)度為6+4=10。2V1V2741V3V45631演算法簡(jiǎn)介46有向圖的最短路徑問(wèn)題有向圖的最短路徑問(wèn)題cont.n假設(shè)圖形有n個(gè)頂點(diǎn)分別是V1, , Vn。n令dk

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

26、7335407354074347043470d41234101622107335407434702V1V2741V3V45631演算法簡(jiǎn)介48有向圖的最短路徑問(wèn)題有向圖的最短路徑問(wèn)題cont.n假設(shè)Vi到Vj的最短路徑經(jīng)過(guò)Vk則Vi到Vk的路徑也是最短的路徑而Vk到Vj的路徑也是最短的。n例如由V2到V4的最短路徑為V2, V1, V4而路徑V2, V1也是V2到V1的最短路徑而路徑V1, V4也是V1到V4的最短路徑n最正確解包含其組成份子的最正確解之特性稱為最正確化原則最正確化原則 Principle of Optimalityn假如最正確化問(wèn)題能應(yīng)用此最正確化原則則可以用動(dòng)態(tài)規(guī)劃策略設(shè)計(jì)

27、遞迴運(yùn)算式來(lái)求得最正確解演算法簡(jiǎn)介4920.5 刪除與搜尋策略刪除與搜尋策略Prune-and-Search Method n包含屢次的處理，每次的處理都會(huì)將輸入資料刪除固定的百分比，並運(yùn)用同樣的方法遞迴地以刪除後的資料當(dāng)作輸入資料重新解問(wèn)題，經(jīng)過(guò)假設(shè)干次處理後，資料量將可縮小到能用固定常數(shù)的時(shí)間解得答案nExample：二元搜尋法的每個(gè)步驟能去除一半的資料，是典型的刪除與搜尋演算法演算法簡(jiǎn)介50刪除與搜尋策略刪除與搜尋策略cont.找出 n 個(gè)數(shù)的第 k 小的數(shù)n直接的解法：將這 n 個(gè)數(shù)由小到大排好後，然後就能依序找出第 k 小的數(shù)nOnlog2n時(shí)間。n刪除與搜尋策略：On時(shí)間演算法簡(jiǎn)介

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

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