第四講分治策略

1、第4講 分治策略7/23/20221主要內(nèi)容分治法基本思想二分搜索算法合并排序算法快速排序算法線性時間選擇7/23/202224.1 分治法的基本思想例:找偽幣問題給你一個裝有1 6個硬幣的袋子。1 6個硬幣中有一個是偽造的，并且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。為了幫助你完成這一任務，將提供一臺可用來比較兩組硬幣重量的儀器，利用這臺儀器，可以知道兩組硬幣的重量是否相同。7/23/20223一種方式 兩兩對比，找到輕者，最差比較8次另外一種1)將16個硬幣分成A、B兩半；2)將A放儀器的一邊，B放另一邊，如果A袋輕，則表明偽幣在A，解子問題A即可，否則，解子問題B

2、。7/23/20224例25 金塊問題 有一個老板有一袋金塊。每個月將有兩名雇員會因其優(yōu)異的表現(xiàn)分別被獎勵一個金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。根據(jù)這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。如果有新的金塊周期性的加入袋中，則每個月都必須找出最輕和最重的金塊。假設有一臺比較重量的儀器，我們希望用最少的比較次數(shù)找出最輕和最重的金塊。7/23/20225假設袋中有n 個金塊。通過n-1次比較找到最重的金塊。找到最重的金塊后，可以從余下的n-1個金塊中用類似的方法通過n-2次比較找出最輕的金塊。這樣，

3、比較的總次數(shù)為2n-3。n2時，識別出最重和最輕的金塊，做一次比較。 n2時， 第一步，把這袋金塊平分成兩個小袋A和B。 第二步，分別找出在A和B中最重和最輕的金塊。HA 與LA，HB 和LB。 第三步，通過比較HA 和HB，可以找到所有金塊中最重的；通過比較LA 和LB，可以找到所有金塊中最輕的。7/23/20226復雜度設c(n)為比較次數(shù)。假設n是2的冪。當n= 2時，c(n) = 1；當n2時，c(n) = 2c(n/ 2 ) + 2。當n是2的冪時，可知c(n) = 3n/ 2 - 2。使用分而治之方法比逐個比較的方法少用了2 5的比較次數(shù)。7/23/202274.1 分治法的基本思

4、想分而治之方法與軟件設計的模塊化方法非常相似。為了解決一個大的問題，可以： 把它分成兩個或多個更小的問題； 分別解決每個小問題； 把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。7/23/20228原問題子問題1子問題2子問題k子問題1子問題2子問題3相同類型不可再分，直接求解7/23/20229分治法流程用P表示問題的輸入。Divide-and-Conquer(P) if (|P|=n0) Adhoc(P); divide P into smaller subinstances P1,P2,Pk; for(i=1;i1解上式得到7/2

5、3/2022134.2 二分搜索技術 給定已排好序的n個元素a0:n-1，現(xiàn)要在這n個 元素中找出一特定元素x，找到則將其位置賦于變 量j中，否則j置-1。如果只允許進行元素間的比較而不允許對它們進行其它的運算，則所設計的算法稱為以比較為基礎的算法。問題提出7/23/2022141 線性搜索 線性搜索二元比較樹如下： x:A2x:An不成功不成功不成功x:A1不成功任何以比較為基礎的搜索算法的執(zhí)行過程都可以用一棵二元比較樹來描述。每次可能的比較用一個內(nèi)頂點表示，對應于不成功的結果有一個外頂點與之對應。 An-1xAn7/23/202215線性算法復雜度該方法沒有很好利用已經(jīng)排好序這個條件，順序

6、搜索方法平均需要 O(n)次比較。7/23/2022162 二分搜索方法基本思想 取一個中間元素做比較元素，如果x等于它，則結束，如果小于，去左半部查找，否則去右半部搜索將問題表示為：I=(n,a1,an,x) 選取一個下標k，可得到三個子問題： I1=(k-1,a1,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,an,x)ak7/23/202217二元比較樹含9個元素的情況4650287137/23/202218二元比較樹x:A(n-1)/2x:A(n-3)/4x:A(3n-1)/4x:A(n-1)/2-1x:A(n-1)/2+1x:A0 x:An-1不成功不成功不成功不成功

7、不成功不成功不成功不成功7/23/202219例2-6 在9,12,15,27,39中分別查找27，12，149 12 15 27 390 1 2 3 4 left right midmid = (left+right)/2=(0+4)/2=2mid =(3+4)/2=39 12 15 27 39leftrightmid查找27成功返回3，leftrightmid9 12 15 27 39leftright7/23/202220template int BinarySearch( T a, const T& x, int n) /在a0=a1=amiddle) left= ; else rig

8、ht= ; return 1; /未找到xn-10left=right(left+right)/2middle+1middle 17/23/202221例:-15,-6,0,7,9,23,54,82,101中查找101，-14，82X=101Low high mid0 8 45 8 67 8 78 8 8 OKX=-14Low high mid0 8 40 3 10 0 0 0 NOX=82Low high mid0 8 45 8 67 8 7 OK7/23/202222二分搜索所需的空間和時間所需空間存放數(shù)組a的地址，還有l(wèi)eft，right，middle，及x的地址需要存儲，共10字節(jié)計算

9、時間成功檢索的最好情況和不成功檢索的最好情況成功檢索的平均情況和不成功檢索的平均情況成功檢索的最壞情況和不成功檢索的最壞情況7/23/202223成功檢索最好情況和不成功檢索最好情況成功檢索共有n種不成功檢索共有n+1種元素 2 5 6 7 9 23 54 82 101 a 0 1 2 3 4 5 6 7 8 3 3 3 4 4 3 3 3 4 4比較次數(shù) 3 2 3 4 1 3 2 3 4 成功比較次數(shù)不成功比較次數(shù)4650287137/23/202224由圖可見，當x在數(shù)組A中時，算法在圓形頂點結束；不在A中時，算法在方形頂點結束。因為23924，所以比較樹的葉頂點都在4或5級上出現(xiàn)。因而元素比較的最多次數(shù)為4。一般地有：當 時，一次成功的折半搜索至多做k次比較，而一次不成功的折半搜索或者做k-1次比較，或者做k次比較。7/23/202225二分搜