計(jì)算機(jī)算法設(shè)計(jì)與分析第2版2遞歸與分治策略-文庫吧在線文庫
【正文】 k1 2k1 子棋盤 (a)所示。 dc tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc, dr, dc, s)。} // 覆蓋左下角子棋盤 if (dr = tr + s amp。 else {// 用 t 號(hào) L型骨牌覆蓋左上角 board[tr + s][tc + s] = t。 //復(fù)制回?cái)?shù)組 a } } 復(fù)雜度分析 T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法 ??????? 11)()2/(2)1()(nnnOnTOnT合并排序 算法 mergeSort的遞歸過程可以消去。 while (a[ j] x)。 ji{5, 6, 5, 2, 7, 8} j。 ?最壞時(shí)間復(fù)雜度： O(n2) ?平均時(shí)間復(fù)雜度： O(nlogn) ?輔助空間： O(n)或 O(logn) 線性時(shí)間選擇 給定線性序集中 n個(gè)元素和一個(gè)整數(shù) k， 1≤k≤n，要求找出這 n個(gè)元素中第 k小的元素 templateclass Type Type RandomizedSelect(Type a[],int p,int r,int k) { if (p==r) return a[p]。由此可得 T(n)=O(n)。同理，基準(zhǔn)x也至少比 3(n5)/10個(gè)元素小。 //找中位數(shù)的中位數(shù)， rp4即上面所說的 n5 Type x = Select(a, p, p+(rp4)/5, (rp4)/10)。 最接近點(diǎn)對(duì)問題 給定平面上 n個(gè)點(diǎn)的集合 S，找其中的一對(duì)點(diǎn)，使得在 n個(gè)點(diǎn)組成的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)間的距離最小。由圖可以看出， 如果 (md,m]中有 S中的點(diǎn)，則此點(diǎn)就是 S1中最大點(diǎn)。 ?能否在線性時(shí)間內(nèi)找到 p,q？ 最接近點(diǎn)對(duì)問題 ?考慮 P1中任意一點(diǎn) p，它若與 P2中的點(diǎn) q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有 distance(p， q)＜ d。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對(duì)候選者的 S2中點(diǎn)一定在矩形 R中，所以它們?cè)谥本€ l上的投影點(diǎn)距 p在 l上投影點(diǎn)的距離小于 d。 d2=cpair2(S2)。 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 課后作業(yè) ? 習(xí)題 28， 29， 210， 227， 230， 231， 232。 } 復(fù)雜度分析 T(n)=O(nlogn) ??????? 44)()2/(2)1()(nnnOnTOnT循環(huán)賽日程表 設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他 n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行 n1天。 最接近點(diǎn)對(duì)問題 最接近點(diǎn)對(duì)問題 double cpair2(S) { n=|S|。若矩形 R中有多于 6個(gè) S中的點(diǎn)，則由鴿舍原理易知至少有一個(gè) (d/2) (2d/3)的小矩形中有 2個(gè)以上 S中的點(diǎn)。 ?選取一垂直線 l:x=m來作為分割直線。 ?假設(shè)我們用 x軸上某個(gè)點(diǎn) m將 S劃分為 2個(gè)子集 S1和 S2 ， 基于 平衡子問題 的思想，用 S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。 } 復(fù)雜度分析 T(n)=O(n) ???????? 7575)4/3()5/()( 21nnnTnTnCCnT上述算法將每一組的大小定為 5，并選取 75作為是否作遞歸調(diào)用的分界點(diǎn)。 }。如果?n/5?是偶數(shù)，就找它的 2個(gè)中位數(shù)中較大的一個(gè)。 } 在最壞情況下，算法 randomizedSelect需要 O(n2)計(jì)算時(shí)間 但可以證明，算法 randomizedSelect可以在 O(n)平均時(shí)間內(nèi)找出 n個(gè)輸入元素中的第 k小元素。 return Partition (a, p, r)。 a[j] = x。 //對(duì)左半段排序 QuickSort (a,q+1,r)。 //取中點(diǎn) mergeSort(a, left, i)。 // 覆蓋其余方格 chessBoard(tr+s, tc, tr+s, tc+s1, s)。amp。 棋盤覆蓋 void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return?；蛟S應(yīng)當(dāng)研究３ ３或５ ５矩陣的更好算法。 大整數(shù)的乘法 請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè) n位大整數(shù)的乘法運(yùn)算 ?小學(xué)的方法： O(n2) ?效率太低 ?分治法 : O() ?較大的改進(jìn) ?更快的方法 ?? ?如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。 if (x a[m]) r = m1。 分析： 很顯然此問題分解出的子問題相互獨(dú)立，即在 a[i]的前面或后面查找 x是獨(dú)立的子問題，因此滿足分治法的第四個(gè)適用條件。設(shè)分解閥值 n0=1，且 adhoc解規(guī)模為 1的問題耗費(fèi) 1個(gè)單位時(shí)間。 這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然也可用分治法，但一般用 動(dòng)態(tài)規(guī)劃 較好。 采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。 由此可見， n個(gè)圓盤的移動(dòng)問題可分為 2次 n1個(gè)圓盤的移動(dòng)問題，這又可以遞歸地用上述方法來做。開始時(shí)，在塔座 a上有一疊共 n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。 遞歸的概念 例 5 整數(shù)劃分問題 前面的幾個(gè)例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 (2) q(n,m)=q(n,n),m?n。 設(shè) R={r1,r2,… ,rn}是要進(jìn)行排列的 n個(gè)元素， Ri=R{ri}。 ? M=3時(shí)，類似的可以推出 ? M=4時(shí)， A(n,4)的增長速度非常快，以至于沒有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。 下面來看幾個(gè)實(shí)例。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 算法總體思想 ? 將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 ? （ 1）二分搜索技術(shù)； ? （ 2）大整數(shù)乘法； ? （ 3） Strassen矩陣乘法； ? （ 4）棋盤覆蓋； ? （ 5）合并排序和快速排序； ? （ 6）線性時(shí)間選擇； ? （ 7）最接近點(diǎn)對(duì)問題； ? （ 8）循環(huán)賽日程表。 ? 將要求解的較大規(guī)模的問題分割成 k個(gè)更小規(guī)模的子問題。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1