第三章 遞歸分治策略

高級算法設計與分析

第三章遞歸分治策略方法分治策略分治法效率分析——迭代法（遞歸樹法）分治法效率分析——主定理方法問題最近點對問題凸包問題最大子數(shù)組問題矩陣乘法的Strassen算法主要內(nèi)容將一個問題分解為與原問題相似但規(guī)模更小的若干子問題，遞歸地解這些子問題，然后將這些子問題的解結合起來構成原問題的解。這種方法在每層遞歸上均包括三個步驟：Divide（分解）：將問題劃分為若干個子問題Conquer（求解）：遞歸地解這些子問題；若子問題Size足夠小，則直接解決之Combine（組合）：將子問題的解結合成原問題的解分治策略分治法規(guī)模為n/2的子問題2規(guī)模為n/2的子問題1子問題1的解原問題的解子問題2的解規(guī)模為n的問題遞歸算法！規(guī)模為n/2的子問題2規(guī)模為n/2的子問題1子問題1的解原問題的解子問題2的解規(guī)模為n的問題遞歸算法！遞歸算法一個遞歸算法通常包含遞歸地調用該算法本身，傳入較小的參數(shù)。遞歸算法的中止條件：

處理基本情況，這些情況不可以有任何遞歸調用。例子：求n！intfact(intn){ if(n<=1)return1;

elsereturnn*fact(n-1);}fact(3)321fact(2)fact(1)returns61**267歸并排序83297154832971548329715483297154382917452389145712345789883297154832971548329715483297154382917452389145712345789歸并排序輸入數(shù)組A[p..r]，進行遞歸排序：

用遞歸式分析分治算法的運行時間。一個遞歸式是一個函數(shù)，它由一個或多個基本情況（basecase），它自身，以及小參數(shù)組成。遞歸式的解可以用來近似算法的運行時間。分治算法的效率分析例子：求n！intfact(intn){ if(n<=1)return1;

elsereturnn*fact(n-1);}遞歸關系式:遞歸式求解方法1——迭代法(1)當n>1時T(n)=T(n-1)+1=T(n-2)+1+1=…=T(1)+1+…+1=T(1)+n-1=n歸并排序輸入數(shù)組A[p..r]，遞歸排序兩個分組，并將結果組合排序：遞歸式:

遞歸式求解方法1——迭代法(2)遞歸樹法遞歸樹給出了遞歸算法中各個過程運行時間的估計。遞歸樹每次在深度上擴展一層。

遞歸式T(n)=kT(n/m)+f(n)中每次遞歸調用用一個結點表示，結點包含非遞歸操作次數(shù)f(n)。

例如:T(n)=2T(n/2)+cn,非遞歸部分為cn，cn就是節(jié)點下面的值。每個節(jié)點的分支數(shù)為k每層的右側標出當前層中所有節(jié)點的和。將所有層總的操作次數(shù)相加。歸并排序的遞歸樹初始的遞歸樹只有一個結點，包含調用

MS(n),最壞情況下的合并代價是

cn.當展開計算，該節(jié)點變成一顆子樹:子樹的根結點包含調用MS(n),和非遞歸的操作

cn.兩個孩子結點各包含一個遞歸調用MS(n/2),最壞情況下的合并代價是

c(n/2)。

MS(n)cndepth 節(jié)點數(shù)

T(n)01

cnMS(n)cnMS(n/2)c(n/2)歸并排序第一層展開122c(n/2)MS(n/2)c(n/2)01

cn歸并排序第二層展開244c(n/4)MS(n/2)cn/2MS(n/4)c(n/4)MS(n/4)c(n/4)MS(n/2)cn/2MS(n/4)c(n/4)MS(n/4)c(n/4)MS(n)cn12cn+depth 節(jié)點數(shù)

T(n)01

cn歸并排序第三層展開388c(n/8)MS(n/2)cn/2MS(n/4)cn/4MS(n/4)cn/4MS(n/2)cn/2MS(n/4)cn/4MS(n/4)cn/4MS(n)cn12

cn+24

cn

+++MS(n/8)cn/8MS(n/8)cn/8MS(n/8)cn/8.......depth節(jié)點數(shù)

T(n)歸并排序最后中止展開簡化n=2k

lgn=k.當一個結點調用MS(n/2k):歸并排序輸入的規(guī)模為n/2k

=

1.這種情況下展開中止,該節(jié)點為葉子結點，代價是

(1)01cn12cn222

cn323

cnT(n)=(k+1)(cn)

=(lgn+1)(cn)

=Q(nlgn)

cn/20cn/21cn/21cn/22)cn/22cn/22cn/22cn/23cn/23cn/23cn/23cn/23cn/23cn/23cn/23

cck2k

cndndT(n)歸并排序完整的遞歸樹舉例:T(n)=2T(n/2)+n2n2

c(n/2)

c(n/2)

Letn=2k.Thenk=lgn,n/2k=1,c(n/2k)=c(1)=(1).n2

(n/2)2

c(n/4)

(n/2)2

c(n/4)c(n/4)c(n/4)第一層展開:第二層展開:遞歸樹T(n)012lgnn2

(n/2)2(n/2)2(n/4)2(n/4)2(n/4)2(n/4)2

n2

(1/2)n2

(1/4)n2

......將遞歸樹的所有層代價累加起來，得：舉例:T(n)=2T(n/2)+n2遞歸樹T(n)012lgnn2

(n/2)2(n/2)2(n/4)2(n/4)2(n/4)2(n/4)2

n2

(1/2)n2

(1/4)n2

......將遞歸樹的所有層代價累加起來，得：舉例:T(n)=2T(n/2)+n2用遞歸樹方法解T(n)=2T(n/2)+n/lgn:

在深度i,有2i

結點,每個是(n/2i)/lg(n/2i)=(n/2i)/(lgn–i)

深度

i

的代價是2i(n/2i)/(lgn–i)=n/(lgn–i)舉例:T(n)=2T(n/2)+n/lgn把每一層的運行代價加起來：

調和級數(shù):舉例:T(n)=2T(n/2)+n/lgn遞歸式求解方法2——主定理法（1）該方法可解如下形式的遞歸式：

T(n)=aT(n/b)+f(n)其中a

31和b>1是兩個常數(shù),f(n)是一個漸進非負函數(shù)（當n趨于無窮時，f(n)是非負的）。如果

n/b

不是整數(shù),取整n/b

：主方法可解包含三種類型

f(n)的遞歸式

T(n)。

遞歸式求解方法2——主定理法（2）正則條件理解主定理（1）關鍵是看f(n)和nlogba

誰比較大。Case1成立，如果nlogba

較大

T(n)=

(nlogba).“較大”指多項式意義上的大,大一個因子n

,forsome>0.例如：理解主定理（2）Case2(當k=0)成立，如果f(n)和nlogba

大小相當。這種情況，乘以一個對數(shù)因子

T(n)=

(f(n)lgn).一般來說,當f(n)和nlogbalgkn

大小相當

T(n)=

(f(n)lgk+1n).Case2的特殊情況:k=0理解主定理（3）例：理解主定理（4）Case3成立，如果f(n)is較大

T(n)=

(f(n)).Case3要滿足正則條件（regularitycondition）.正則條件對于f(n)=nkandf(n)=(nlogba+

)存在>0總是成立的。例正則條件(1)正則條件是什么?1.在遞歸式T(n)=aT(n/b)+f(n)中,f(n)可以直觀的被解釋為把一個規(guī)模為n的問題分解成a個規(guī)模為n/b的子問題和合并a個子問題的解的代價2.af(n/b)可以被解釋為把a個規(guī)模為n/b的子問題分解成a2個規(guī)模為n/b2的子問題和合并a2個子問題解的代價。

條件af(n/b)≤cf(n),forc<1和足夠大的n,可以被解釋為上述第一點的代價是上述第二點代價的準確界。

當一個問題被分解成越來越小的子問題，分解和合并的代價變得越來越小。主定理主定理另一種形式:舉例1遞歸式T(n)=5T(n/2)+n2.

其中a=5，b=2.

因為log25>log24,=log25–log24>0.

因為f(n)=n2=nlog25–

O(nlog25–

),

根據(jù)主定理Case1

T(n)=

(nlog25).舉例2遞歸式T(n)=27T(n/3)+n3lgn

其中a=27，b=3.

因為nlog327=n3,f(n)=n3lgn=nlog327lgn.

根據(jù)主定理Case2中k=1

T(n)=

(n3lg2n).舉例3遞歸式T(n)=5T(n/2)+n3.

其中a=5，b=2.因為3=log28>log25,=log28–log25>0.

f(n)=n3=nlog25+

(nlog25+

),af(n/b)=5f(n/2)=5(n/2)3=5n3/8

cn3for

c=5/8<1根據(jù)主定理Case3

T(n)=

(n3).舉例4

遞歸式T(n)=2T(n/2)+n/lgn,其中a=2，b=2

nlog22=

n.f(n)=nlg–1n

不屬于O(nlogba

–

)=O(n1–

)for

>0盡管nlogba>f(n),但不是多項式意義上的大

主定理Case1不適用。f(n)=nlg–1n不屬于(nlogbalgkn)foranyk≥0

主定理Case2不適用。f(n)=nlg–1n不屬于(nlogba+

)=(n1+

)for

>0

主定理Case3不適用。

T(n)不能用主定理解。改變變量

39P1(x1,y1),...,Pn=(xn,yn)是平面上n個點構成的集合S，假設n=2k，最近點對問題要求找出距離最近的兩個點。最近點對問題是許多算法的基本步驟。二維最近點對問題將點集S分為S1和S2，分隔線是S在x軸的中點（如何確定x=c?）遞歸求解S1和S2的最近點對，令d=min{d1,d2}，確定C1和C2將C1和C2的最近點對合并。x=cd1d2d=min{d1,d2}d=min{d1,d2}C1C2二維最近點對問題x=cd1d2d=min{d1,d2}d=min{d1,d2}C1C2二維最近點對問題42二維最近點對問題在合并兩個子集C1和C2時，對于C1中的每個點P(x,y)，都須要檢查C2中的點和P之間的距離是否小于d。假設p在C1中，在C2中與p距離小于d的點不會超過六個最多進行6*n/2次比較43二維最近點對問題

pd極端情況一共6個可能的對比點極端情況p在分界線上計算時間：合并最小問題所花的時間為M(n)=O(n)該算法的最差遞歸時間為：T(n)=2T(n/2)+n=O(nlogn)二維最近點對問題最大子數(shù)組問題問題:輸入:數(shù)值數(shù)組A[1..n]假設數(shù)組中存在負數(shù)如果數(shù)組中全是非負數(shù)，該問題很簡單。輸出:數(shù)組下標

i

和

j

使得子數(shù)組

A[i..j]為A[1..n]的和最大的非空連續(xù)子數(shù)組。最大子數(shù)組問題應用考慮下面的情景:一支股票連續(xù)n天的交易價格。什么時間該買入?什么時間該賣出?如何將這個問題轉換成最大子數(shù)組問題?定義:A[i]=(第i天的價格)–(第i–1天的價格)。如果最大子數(shù)組是A[i..j],則

第i天買入,第j

天后賣出。最大子數(shù)組問題應用一支股票連續(xù)n天的交易價格:最大子數(shù)組是A[3..3].Day01234Price10117106Change1-43-4最后一行是

A.最大子數(shù)組問題應用一支股票連續(xù)n天的交易價格:最大子數(shù)組是A[8..11].LastrowisA.蠻力法蠻力法:首先找出所有可能的子數(shù)組子數(shù)組的個數(shù)?然后計算每個子數(shù)組的和對于每一個子數(shù)組，需要做多少次加法?取決于子數(shù)組的大小:從0到n–1.至少是

(1).最后找出最大的和:(n2).蠻力法需要(n2)時間.如何算得更快?分治算法子問題:

找出A[low..high]的最大子數(shù)組。參數(shù)初始值,low=1,high=n.分解將子數(shù)組分解成兩個大小基本相同的子數(shù)組找到子數(shù)組的中間位置

mid，將子數(shù)組分成兩個更小的子數(shù)組A[low..mid]

和A[mid+1..high]。求解找數(shù)組A[low..mid]

和

A[mid+1..high]的最大子數(shù)組。組合找出跨越中間位置的最大子數(shù)組。

三種情況取和最大的子數(shù)組(跨越中間位置的最大子數(shù)組和求解步驟中找到的兩個最大子數(shù)組)。找跨越中間位置的最大子數(shù)組這是一個關鍵的新問題。它不是原問題的一個小規(guī)模實例，附加限制：子數(shù)組必須跨越中間位置。這個問題可以用(n)

時間解決。任何一個跨越中間位置A[mid]的子數(shù)組A[i..j]由兩個更小的子數(shù)組A[i..mid]和A[mid+1..j]組成,其中l(wèi)ow

i

mid<j

high.因此，只需要找兩種形式的最大子數(shù)組A[i..mid]和A[mid+1..j],然后把它們合并。算法：找跨越中間位置的最大子數(shù)組運行時間分析:兩個循環(huán)總共考慮[low..high]中的每個數(shù)組下標一次，每次迭代需要

(1)時間

整個過程需要

(n)時間.最大子數(shù)組問題分治算法Initialcall:Find-Maximum-Subarray(A,1,n)算法分析簡化假設:原始問題的規(guī)模是2的冪,所有子問題的規(guī)模是整數(shù).用

T(n)表示最大子數(shù)組算法在n個元素數(shù)組上的運行時間基本情況:當high=low,n=1。算法什么也不做就返回

T(n)=(1)。遞歸情況:當n>1分解需要(1)

時間.求解兩個子問題,每個子問題有n/2元素，需要T(n/2)時間

總共需要2T(n/2)時間。合并包括調用跨越中間位置最大子數(shù)組,需要(n)

時間,和常數(shù)時間的測試

(n)+(1)。算法分析(續(xù))遞歸情況的遞歸式

T(n)=(1)+2T(n/2)+(n)+(1)=2T(n/2)+(n)所有情況的遞歸式和歸并排序的遞歸式相同.

和歸并排序運行時間相同:T(n)=(nlgn).最大子數(shù)組分治算法運行時間為(nlgn)，比蠻力法

(n2)快。56Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：由此可得：T(n)=8T(n/2)+(n2)57Strassen矩陣乘法為了降低時間復雜度，必須減少乘法的次數(shù)。58Strassen矩陣乘法時間的遞推關系式當n>1時，M(n)=7M(n/2)，M(1)=1因為n=2k，M(n)=7M(n/2)=72M(n/22)…… =7kM(1)=7kM(n)=7log2n=nlog27≈n2.807Hopcroft和Kerr已經(jīng)證明(1971)，計算2個２×２矩陣的乘積，7次乘法是必要的。因此，要想進一步改進矩陣乘法的時間復雜性，就不能再基于計算2×2矩陣的7次乘法這樣的方法了?；蛟S應當研究３×３或５×５矩陣的更好算法。在Strassen之后又有許多算法改進了矩陣乘法的計算時間復雜性。目前最好的計算時間上界是O(n2.376)是否能找到理論下界O(n2)的算法？？？目前為止還沒有結果。凸包問題(ConvexHullsProblem)AlgorithmSpeedDiscoveredByBruteForceO(n3)[Anon,thedarkages]GiftWrappingO(nh)[Chand&Kapur,1970]GrahamScanO(nlogn)[Graham