計(jì)算機(jī)算法設(shè)計(jì)與分析第2版2遞歸與分治策略-免費(fèi)閱讀
【正文】 遞歸地用對(duì)選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。 m=S中各點(diǎn) x間坐標(biāo)的中位數(shù) 。這與 d的意義相矛盾。由此將 S分割為 S1和 S2。 ?能否在線性時(shí)間內(nèi)找到 p3,q3？ 最接近點(diǎn)對(duì)問題 ?如果 S的最接近點(diǎn)對(duì)是 {p3,q3}，即 |p3q3|d，則 p3和 q3兩者與 m的距離不超過 d， 即 p3∈ (md,m]， q3∈ (m,m+d]。這是使 T(n)=O(n)的關(guān)鍵之處。 i=(rp4)/5。 線性時(shí)間選擇 設(shè)所有元素互不相同。 例如，若 ε=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短 1/10。通過修改算法 partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。 } 初始序列 {6, 7, 5, 2, 5, 8} j。 Type x=a[p]。 merge(a, b, left, i, right)。amp。 else {// 此棋盤中無特殊方格 // 用 t 號(hào) L型骨牌覆蓋左下角 board[tr + s 1][tc + s] = t。 // 分割棋盤 // 覆蓋左上角子棋盤 if (dr tr + s amp。目前最好的計(jì)算時(shí)間上界是 O() ?是否能找到 O(n2)的算法？ 棋盤覆蓋 在一個(gè) 2k 2k 個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。該方法也可以看作是一個(gè)復(fù)雜的分治算法。 } return 1。 分析： ? 該問題的規(guī)?？s小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個(gè)規(guī)模較小的相同問題 。用 T(n)表示該分治法解規(guī)模為 |P|=n的問題所需的計(jì)算時(shí)間，則有： 11)()/()1()(???????nnnfmnkTOnT通過迭代法求得方程的解： ? ????1l o g0l o g )/()(nmjjjkm mnfknnT注意 ： 遞歸方程及其解只給出 n等于 m的方冪時(shí) T(n)的值，但是如果認(rèn)為 T(n)足夠平滑，那么由 n等于 m的方冪時(shí) T(n)的值可以估計(jì) T(n)的增長速度。 //解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,...,Pk； //分解問題 for (i=1,i=k,i++) yi=divideandconquer(Pi)。 用遞推來實(shí)現(xiàn)遞歸函數(shù)。 遞歸的概念 例 6 Hanoi塔問題 void hanoi(int n, int a, int b, int c) { if (n 0) { hanoi(n1, a, c, b)。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則： 規(guī)則 1：每次只能移動(dòng) 1個(gè)圓盤； 規(guī)則 2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則 3：在滿足移動(dòng)規(guī)則 1和 2的前提下，可將圓盤移至 a,b,c中任一塔座上?？梢越?q(n,m)的如下遞歸關(guān)系。因此， q(1,m)=1。 (ri)perm(X)表示在全排列 perm(X)的每一個(gè)排列前加上前綴得到的排列。 ? 定義其擬逆函數(shù) α(n) 為： α(n)=min{k ｜A(k)≥n} 。 遞歸的概念 例 2 Fibonacci數(shù)列 無窮數(shù)列 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， …… ，稱為Fibonacci數(shù)列。 遞歸的概念 ? 直接或間接地調(diào)用自身的算法稱為 遞歸算法 。 算法總體思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = ? 對(duì)這 k個(gè)子問題分別求解。 ? 通過下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。 算法總體思想 ? 將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 ? 分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。 遞歸的概念 例 3 Ackerman函數(shù) ? A(n， m)的自變量 m的每一個(gè)值都定義了一個(gè)單變量函數(shù)： ? M=0時(shí)， A(n,0)=n+2 ? M=1時(shí)， A(n,1)=A(A(n1,1),0)=A(n1,1)+2，和 A(1,1)=2故A(n,1)=2*n ? M=2時(shí)， A(n,2)=A(A(n1,2),1)=2A(n1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故 A(n,2)= 2^n 。 遞歸的概念 例 4 排列問題 設(shè)計(jì)一個(gè)遞歸算法生成 n個(gè)元素 {r1,r2,… ,rn}的全排列。 例如正整數(shù) 6有如下 11種不同的劃分： 6； 5+1； 4+2， 4+1+1； 3+3， 3+2+1， 3+1+1+1； 2+2+2， 2+2+1+1， 2+1+1+1+1； 1+1+1+1+1+1。 正整數(shù) n的劃分由 n1=n的劃分和 n1≤n 1的劃分組成。 遞歸的概念 例 6 Hanoi塔問題 設(shè) a,b,c是 3個(gè)塔座。此時(shí)若能設(shè)法將 n1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座 a移至塔座 c，然后，將剩下的最大圓盤從塔座 a移至塔座 b，最后，再設(shè)法將 n1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座 c移至塔座 b。 解決方法： 在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。 這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用 能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮 貪心算法 或 動(dòng)態(tài)規(guī)劃 。 分治法的復(fù)雜性分析 一個(gè)分治法將規(guī)模為 n的問題分成 k個(gè)規(guī)模為 n／ m的子問題去解。這就說明了此問題滿足分治法的第二個(gè)和第三個(gè)適用條件。 if (x == a[m]) return m。 1. XY = ac 2n + ((ac)(bd)+ac+bd) 2n/2 + bd 2. XY = ac 2n + ((a+c)(b+d)acbd) 2n/2 + bd 復(fù)雜度分析 T(n)=O(nlog3) =O()?較大的改進(jìn) 11)()2/(3)1()(??????? nnnOnTOnT細(xì)節(jié)問題 ：兩個(gè) XY的復(fù)雜度都是 O(nlog3)，但考慮到 a+c,b+d可能得到 m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第 2種方案。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算 2 2矩陣的 7次乘法這樣的方法了。遞歸地使用這種分割，直至棋盤簡化為棋盤 1 1。} // 覆蓋右上角子棋盤 if (dr tr + s amp。 else {// 用 t 號(hào) L型骨牌覆蓋右上角 board[tr + s][tc + s 1] = t。 void MergeSort(Type a[], int left, int right) { if (leftright) {//至少有 2個(gè)元素 int i=(left+right)/2。 QuickSort (a,p,q1)。 } a[p] = a[j]。 Swap(a[i], a[p])。 else return RandomizedSelect(a,i+1,r,kj)。 ?遞歸調(diào)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1