【正文】 ? 構造遞歸樹的方法就是展開遞歸方程，然后將樹中每層的時間求和，最終獲得算法的時間復雜性。 ?適用比較容易猜出遞歸解的情形。用 T(n)表示該分治算法解規(guī)模為 |P|=n的問題所需的計算時間，則有下列遞歸方程： ( 1 ) 1()( ) ( ) 1OnTnaT n b f n n???? ???通過求解遞歸方程得到遞歸算法的時間復雜性。設分解閾值 n0=1，且 adhoc解規(guī)模為 1的問題耗費 1個單位時間。//遞歸的 求解 各子問題 return merge(y1,...,ya)。 —— 《算法分析與設計》 6 分治算法的算法框架 divideandconquer(P){ if ( | P | = n0) adhoc(P)。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解 。 ( 1 ) 1()( ) ( ) 1nTnaT n b f n n? ??? ???? 最頂層問題 a 為分解的子問題數(shù)量； n/b 為每個子問題的數(shù)據(jù)規(guī)模； f(n) 為合并子問題解所消耗的時間。—— 《算法分析與設計》 1 第 2講分治與遞歸策略 ? 分治算法的基本思想 ? 遞歸概念 ? 典型分治算法舉例 —— 《算法分析與設計》 2 算法總體思想 將一個難以直接解決的規(guī)模較大的問題分解為若干個規(guī)模較小的子問題，并 各個擊破，分而治之 。 n/16 n n/4 n/4 n/4 n/4 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 —— 《算法分析與設計》 3 將求出的較小規(guī)模的問題解合并成一個較大規(guī)模的問題解，并 自底向上 地求出原問題的解。 —— 《算法分析與設計》 4 分治算法的基本思想 分治算法的基本思想是將一個規(guī)模為 n的問題分解為 a個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。 —— 《算法分析與設計》 5 分治算法所能解決問題一般具有以下幾個特征： 縮小問題規(guī)?？梢越档徒鉀Q問題的難度； 可以將子問題的解合并為原問題解； 問題分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 //解決規(guī)模小的問題 //將問題 P 分解 為子問題 P1,P2,...,Pa； for (i=1,i=a,i++) yi=divideandconquer(Pi)。 //合并 為原問題的解 } —— 《算法分析與設計》 7 一個分治算法將規(guī)模為 n的問題分成 a個規(guī)模為n／ b的子問題。再設將原問題分解為 a個子問題以及用 merge將 a個子問題的解合并為原問題的解需用 f(n)個單位時間。 分治算法的復雜性分析 —— 《算法分析與設計》 8 ?替換方法 ?遞歸樹方法 ?公式法 求解遞歸方程的三種方法： —— 《算法分析與設計》 9 替換方法 ?替換方法的主要思想是首先推測出遞歸方程的解 ，然后代入遞歸方程，查看是否滿足條件。 ① 猜測出遞歸解的形式 ② 用數(shù)學歸納法找出使解真正有效的常數(shù) ? 替換方法解遞歸方程的基本步驟： —— 《算法分析與設計》 10 例： T(n)=2T(n/2)+n （ 2路歸并 ) 假設解對 n/2成立，即 T(n/2) ≤c(n/2)lg(n/2) 將其對遞歸方程進行替換，得： T(n)= 2T(n/2)+n ≤2(c(n/2)lg(n/2))+n ≤lg(n/2)+n ≤lgn lg2+n = lgn+n 當 c≥1 時，顯然 lgn+n ≤lgn 根據(jù) O符號定義，證明猜測正確。 ?用遞歸樹方法求解遞歸方程的基本步驟 : ?遞歸樹可以方便地推測遞歸方程的解，是描述分治算法的運行時間復雜性的有效手段。第 1層有 3個節(jié)點，第 2層有 32個節(jié)點，依次類推，第 k層有3k個節(jié)點，當 k=log4n，即為葉節(jié)點，因此，葉節(jié)點的個數(shù)為 ，而每個葉節(jié)點需要的時間為 T(1),因此，整個葉節(jié)點的時間為 。 3lognlog 44 n? )1(n 3log 4 T—— 《算法分析與設計》 15 將遞歸樹每一層的時間累加，可得： ? ? ? ?? ? ? ?? ?? ?? ? ? ?)(16316311163163)(23log23log23log23log21log044444nOnnnnnTiini??????????????????i=0 ? 所以，由遞歸樹猜測 T(n)=O(n2)隨后，再利用數(shù)學歸納法證明。 n/b可以是 ，也可以是 ( 1 ) 1()( ) ( ) 1OnTnaT n b f n n???? ???? ?bn/? ?bn/公式法 上述方程描述了如下算法的運行時間：將一個規(guī)模為 n的問題劃分為 a個規(guī)模為 n/b的子問題，其中 a和 b為正常數(shù)。劃分原問題和合并子問題的解所需要的時間由 f(n)決定 —— 《算法分析與設計》 17 定理：上述遞歸方程含有三種情形的漸進界： （ 1）對于某個常數(shù) 如果 則 （ 2）如果 則 （ 3）對某個常數(shù) 如果 且對某個常數(shù) c 1 以及任意足夠大的n, 有 af(n/b)≤cf(n), 則 0?? )()( logn abOnf ? )()( logn abnT ?? )()( logn abnf ?? )lg()( log nnT n ab??))(()( nfnT ??0?? )log()( ???? annf b—— 《算法分析與設計》 18 定理含義 將 f(n)與 進行比較 ， 當 較大時 ， 相等時 當 較小時， )()( logn abnT ?? )lg()( log nnT n ab?? ))(()( nfnT ??結論：可以通過盡量減少子問題的個數(shù)或者減少 f(n)的數(shù)量級來增強分治算法的有效性。 n ablogn ablogn ablog—— 《算法分析與設計》 19 例 1： T(n)=9T(n/3)+n 由上式可知， a = 9， b = 3， f(n) = n, 且 又因為對于 有 滿足定理（ 1），因此， )( 229loglog 3 nOnnn ab ???1?? )()( 9log 3nOnf ??? )()( 2nnT ??—— 《算法分析與設計》 20 例 2： T(n) = T(2n/3)+1 由上式可知 a=1, b=3/2, f(n)=1， 且 又因為 滿足定理（ 2），因此 )(lg)( nnT ??—— 《算法分析與設計》 21 遞歸概念 分治算法 遞歸技術 直接或間接地調用自身的算法稱為 遞歸算法 。 分治算法遞歸技術 分治與遞歸像一對孿生兄弟 分治算法的 特征 ：將較大規(guī)模的問題 分解 為若 干個較小規(guī)模的子問題， 每個子問題的求解過 程與原問題一樣 ，并利用 自底向上 的求解策略 得到最終的解。 無窮 2階數(shù)列 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， … ，被稱為 Fibonacci數(shù)列。 m=3時，類似的可以推出 A(1,0) = 2 A(0,m) = 1 m≥0 A(n,0) = n + 2 n≥2 A(n,m) = A(A(n1,m),m1) n,m≥1 Ackerman函數(shù)的特征： A(n， m)的自變量 m的每一個值都定義了一個單變量函數(shù)。 n個元素的全排列有 n!種可能。 假設集合 Ri中元素的全排列記為 perm(Ri)。 當 n=1時， perm(R)=(r) 其中 r是集合 R中唯一的元素； 當 n1時， perm(R)的全排列為： (r1)perm(R1)， (r2)perm(R2)， … ， (rn)perm(Rn) 方法 1：固定位臵找元素 —— 《算法分析與設計》 27 遞歸公式 —— 《算法分析與設計》 28 —— 《算法分析與設計》 29 將每個元素交換 到固定位臵上， 并求解其余位臵 元素的全排列。 P[m]的全排列時，問題就極為簡單，可作為 遞歸出口。 P[m+1]，通過交換 P[m]和 P[m+1]，這樣我們仍然只要考慮求剩 余元素 P[m+1] 、 P[m+2],… P[n] 的所有排列即可。 —— 《算法分析與設計》 31 —— 《算法分析與設計》 32 void perm(int[] r, int i, int n) { // r存放 R集合元素， r[0]~r[n] // i