計算機算法基礎(chǔ) 第2版 課件 第2章　分治法

1第2

章

分治法分治法原理

2遞推關(guān)系求解

6替換法 7序列求和法和遞歸樹法

10主方法求解 123 例題示范

141.分治法原理當輸入規(guī)模很小時，問題都容易解。當規(guī)模很大時，一個基本方法就是把大規(guī)模問題轉(zhuǎn)換為一組小規(guī)模問題去解。分治法是這種方法之一。分治算法要講明三件事：底：對足夠小的輸入規(guī)模，如何直接解出。

分：如何將規(guī)模為n的輸入分為一組規(guī)模小些的子問題。每個子問題又要遞歸地分解為更小的子問題，直到底為止。被分解的原問題或子問題，稱為那些由它分解得到的子問題的父問題。這里，父子關(guān)系就是分解和被分解的關(guān)系。

合：

如何從子問題的解中獲得它們的父問題的解。合是一個逐層向上的合并過程，直到最初的原問題得解為止。23一個例子：二元搜索Binary-Search(A,p,r,x)輸入：任一段子序列，A[p]≤A[p+1]≤…≤A[r]，和要找的數(shù)字x。輸出:i

如果序列中有A[i]=x，否則nil。

1 ifp>r

//表明數(shù)組為空集2

thenreturn(nil)3 endif4 mid

(p+r)/2

5 if

A[mid]=x6 thenreturn(mid)7

else if

x<A[mid]8

thenBinarySearch(A,p,mid-1,x)9

elseBinarySearch(A,mid+1,r,x)10

endif11 endif12 End4幾點解釋：算法先找出序列的中位數(shù)A[mid]，mid=

(p+r)/2

。如果A[mid]=x，問題解決。否則，原序列一分為二，前一半為A[p..mid-1]，后一半為A[mid+1..r]。如果x<A[mid]，則只需搜索前一半，否則搜索后一半。每遞歸一步，搜索范圍減半，偽碼要適用于不同規(guī)模的子問題。所以，輸入是A[p..r]，而不是A[1..n]。解原問題時，要設(shè)計一個主程序來調(diào)用這個分治算法。例如，算法Binary-Search設(shè)計好之后，主程序需要調(diào)用Binary-Search(A,1,n,x)。分治法只需說清楚如何把A[p..r]分解為A[p..mid-1]和A[mid+1..r]就可以了。把A[p..mid-1]分為更小的子問題由編譯軟件自動完成。軟件會動態(tài)地把r置為mid-1。這時，A[p..r]代表的是A[p..mid-1]。因此，算法只要說清楚如何分解A[p..r]就可以了，千萬不要畫蛇添足。5表示復雜度的遞推關(guān)系因為分治法含有遞歸調(diào)用，所以難以直接計算基本運算的次數(shù)。為得到復雜度，先建立一個表示復雜度的遞推關(guān)系，然后求解得到。以二元搜索為例，A[1..n]中的數(shù)和x之間的比較是主要的基本運算。假設(shè)在最壞情況下，二元搜索需要T(n)次比較，那么我們可以有以下的遞推關(guān)系：T(0)=0 （n=0時，不需比較）T(n)=T(

n/2

)+1 （與x比較一次，再加上子問題需要的比較次數(shù)）一般情況，把規(guī)模為

n的輸入分為規(guī)模為

n/b(b為正整數(shù))的一組子問題，然后解出其中

a個子問題并從而獲得原問題的解，通常有遞推關(guān)系：T(1)=c

（c0，常數(shù)，底的復雜度）T(n)=aT(n/b)+f(n) （

f(n)是分解及合并所需的時間）分治法的復雜度往往需要解以下的遞推關(guān)系： T(1)=c T(n)=aT(n/b)+f(n) 主要方法：替換法:先猜想一個復雜度，然后用歸納法證明其正確。序列求和法從原遞推關(guān)系逐步展開后得一序列，然后對該序列求和后得解。62.遞推關(guān)系求解7解：先證T(n)=O(nlgn)，即存在c>0，使得n

2

時，T(n)≤cnlgn。歸納基礎(chǔ):當

n

=2,3,4時，T(n)=

(1)，故有c>0

使T(n)≤cnlgn?？杉俣╟>1。歸納步驟:假設(shè)當n=2,3,4,…,(k-1)時，T(n)≤cnlgn成立。當n=k(k≥5)時因為

n/2

=

k/2

≤k

-1，由歸納假設(shè)得到

T(

n/2

)≤c(

n/2

)lg(

n/2

)≤c(n/2)lg(n/2)=(cn/2)(lgn-1)。從而，從遞推關(guān)系和c>1得到：T(n)=2T(

n/2

)+n

≤2(cn/2)(lgn-1)+n

=cnlgn

-cn

+n<cnlgn。

歸納成功，故有T(n)=O(nlgn)。

(接下頁)替換法

例2.2 用替換法決定以下遞推關(guān)系表示的算法復雜度

T(n)=

(1)，

當1≤n≤4時，

T(n)=2T(

n/2

)+n

n>48例2.2(繼續(xù)1)再證:存在d>0使得n

2時，T(n)≥d(nlgn+n)=

(nlgn)。歸納基礎(chǔ):當

n

=2,3,4時，因為12

(nlgn

+n)，而T(n)=

(1)，那么，存在足夠小的

d

>0使

T(n)>12d

d(nlgn

+n)?？杉俣?/p>

d

<1/4。歸納步驟:

假定當n=2,3,4,…,(k-1)時，T(n)≥d(nlgn+n）成立。那么，當n

=k時(k

5)時，因為

n/2

=

k/2

≤k-1，由歸納假設(shè)得到：T(

n/2

)≥d[(

n/2

)lg(

n/2

)+

n/2

]d(n/2-1)lg(n/4)+d(n/2–1)

=(dn/2-d)(lgn-2)+dn/2-d

=(dn/2)lgn+2d–dlgn–dn+dn/2–d

>(dn/2)lgn–dlgn–dn/2 >(dn/2)lgn–dn–dn/2 (因為lgn<n)=(dn/2)lgn–3dn/2

(接下頁)9例2.2(繼續(xù)2)

進而從遞推關(guān)系得到：T(n)=2T(

n/2

)+n>2[(dn/2)lgn–3dn/2]+n=dnlgn–3dn+n=dnlgn+dn–4dn+n>d(nlgn+n) (因為d<1/4，–4dn+n>0)歸納成功。這就證明了T(n)=

(nlgn+n)=

(nlgn)，從而有T(n)=

(nlgn)。用替換法解遞推關(guān)系需要猜測出正確的復雜度并且往往需要分別證明上界和下界。當然，很多時候，我們只需對上界作出估計，則可簡化一些工作。另外，該方法需要一定的數(shù)學技巧。本書不常用這個方法。10序列求和法和遞歸樹法兩者的本質(zhì)相同，遞歸樹法用一棵樹把序列產(chǎn)生的過程顯示出來。例2.4

用序列求和法決定由以下遞推關(guān)系表示的算法復雜度

T(1)=O(1)

T(n)=2T(n/2)+nlgn解：置n=2k，得T(2k)=2T(2k-1)+k2k。定義W(k)=T(2k)后，得到：W(k)=2W(k-1)+k2k=2[2W(k-2)+(k-1)2k-1]+k2k

=22W(k-2)+(k-1)2k

+k2k=22

[2W(k-3)+(k-2)2k-2]+(k-1)2k

+k2k=23W(k-3)+(k-2)2k

+(k-1)2k

+k2k=……=2k-1W(1)+2×2k

+3×2k

+…+(k-1)2k

+k2k=2k-1W(1)+2k

[k(k+1)/2-1]=

(k22k)

=

(nlg2n)。11遞歸樹k2kW(k-1)W(k-1)一步遞歸的樹k2k(k-1)2k-1(k-1)2k-1W(k-2)W(k-2)W(k-2)W(k-2)(b) 兩步遞歸樹

(k-2)步遞歸(k-1)2k-1k2k(k-1)2k-1k2k(k-1)2k(k-2)2k-2(k-2)2k-2(k-2)2k-2(k-2)2k-2(k-2)2kW(1)W(1)W(1)W(1)2k-1W(1)(c) 遞歸停止后的完整的遞歸樹12主方法求解

主方法不是一個新的方法。它是用序列求和法時得到的一些結(jié)果的總結(jié)。主要有三條規(guī)則。檢查遞推關(guān)系滿足那條規(guī)則，如滿足，立馬就有答案。設(shè)遞推關(guān)系為T(n)=aT(n/b)+f(n)，a

1,b>1。

用規(guī)則前先計算k值，k=logba。規(guī)則一:如果存在正數(shù)

>0，使得f(n)=O(nk-

)，那么T(n)=

(nk)。例2.5

T(n)=9T(n/3)+nlgn解：

a=9，b=3，k=logba

=lg39=2。

用

=0.2，那么nk-

=n2-0.2

=n1.8。

因為f(n)=nlgn=O(n1.8)，所以T(n)=

(n2)。13

143.

例題示范例2.9給定序列A[1],A[2],…,A[n],請用分治法設(shè)計一個復雜度為O(nlgn)的算法來找出其中兩個序號i<j,使得A[i]

A[j],并使它們的和，A[i]+A[j]，最大。如果沒有這樣兩個數(shù)，則輸出-∞。解：考慮序列A[p..r]。

分為

A[p..mid]和A[mid+1..r]。設(shè) M1=A[i1]+A[j1]是子問題1的解，

M2=A[i2]+A[j2]是子問題2的解。如果

M1

>M2，那么第1個解好些，但不一定是全局最優(yōu)，因為

A[i1]和A[j1]只能取自

A[p..mid]。從

A[p..mid]中取A[i3]，從

A[mid+1..r]中取A[j3]，

M3=A[i3]+A[j3]也許更好。(接下頁)15例

2.9(繼續(xù)1)這樣的解不可能從子問題中得到。所以，在歸遞地解決兩個子問題后，我們還要做額外的工作來彌補缺失的部分。具體做法是：在A[mid+1..r]中找出最大的數(shù)A[j3]。在A[p..mid]中選出所有小于等于A[j3]的數(shù)，組成集合S。(3) S中找出最大的一個數(shù)A[i3]。(4) M3=A[i3]+A[j3]。全局的最優(yōu)解一定產(chǎn)生于M1，M2，M3

之中。這個額外的工作算在分治法的合并部分，不同的問題需要做不同的額外的工作。

16算法偽碼Max-Sum-Two-Numbers(A[p..r],i,j,M) //p≤rifp=r thenM

-∞ //不存在解，是底的情況 elsemid

(p+r)/2

Max-Sum-Two-Numbers(A[p..mid],i1,j1,M1)

Max-Sum-Two-Numbers(A[mid+1..r],i2,j2,M2) findj3suchthatA[j3]=max{A[k]|mid+1≤k≤r}

S

{A[k]|p≤k≤mid,A[k]≤A[j3]}

if|S|=

then

M3