【正文】 最接近點對 {p1,p2}和 {q1,q2}，并設 d=min{|p1p2|,|q1q2|}， S中的最接近點對或者是 {p1,p2}，或者是 {q1,q2}，或者是某個 {p3,q3}，其中 p3∈ S1且 q3∈ S2。 for ( int i = 0。 線性時間選擇 如果能在線性時間內找到一個劃分基準，使得按這個基準所劃分出的 2個子數組的長度都至少為原數組長度的 ε倍 (0ε1是某個正常數 )，那么就可以 在最壞情況下 用 O(n)時間完成選擇任務。 return j。 mergeSort(a, i+1, right)。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s)。 ?在 Strassen之后又有許多算法改進了矩陣乘法的計算時間復雜性。 else l = m+1。再設將原問題分解為 k個子問題以及用 merge將 k個子問題的解合并為原問題的解需用 f(n)個單位時間。該方法通用性強，但本質上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。各圓盤從小到大編號為 1,2,… ,n,現(xiàn)要求將塔座 a上的這一疊圓盤移到塔座 b上，并仍按同樣順序疊置。 最大加數 n1實際上不能大于 n。 ?n2222? 遞歸的概念 例 3 Ackerman函數 ? 定義單變量的 Ackerman函數 A(n)為， A(n)=A(n，n)。 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ī)模較小的相同問題，以便各個擊破， 分而治之。 ? （ 1）二分搜索技術； ? （ 2）大整數乘法； ? （ 3） Strassen矩陣乘法； ? （ 4）棋盤覆蓋； ? （ 5）合并排序和快速排序； ? （ 6）線性時間選擇； ? （ 7）最接近點對問題； ? （ 8）循環(huán)賽日程表。 下面來看幾個實例。 設 R={r1,r2,… ,rn}是要進行排列的 n個元素， Ri=R{ri}。 遞歸的概念 例 5 整數劃分問題 前面的幾個例子中，問題本身都具有比較明顯的遞歸關系，因而容易用遞歸函數直接求解。 由此可見， n個圓盤的移動問題可分為 2次 n1個圓盤的移動問題，這又可以遞歸地用上述方法來做。 這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用 動態(tài)規(guī)劃 較好。 分析： 很顯然此問題分解出的子問題相互獨立，即在 a[i]的前面或后面查找 x是獨立的子問題，因此滿足分治法的第四個適用條件。 大整數的乘法 請設計一個有效的算法，可以進行兩個 n位大整數的乘法運算 ?小學的方法： O(n2) ?效率太低 ?分治法 : O() ?較大的改進 ?更快的方法 ?? ?如果將大整數分成更多段，用更復雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。 棋盤覆蓋 void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return。 // 覆蓋其余方格 chessBoard(tr+s, tc, tr+s, tc+s1, s)。 //對左半段排序 QuickSort (a,q+1,r)。 return Partition (a, p, r)。如果?n/5?是偶數，就找它的 2個中位數中較大的一個。 } 復雜度分析 T(n)=O(n) ???????? 7575)4/3()5/()( 21nnnTnTnCCnT上述算法將每一組的大小定為 5，并選取 75作為是否作遞歸調用的分界點。 ?選取一垂直線 l:x=m來作為分割直線。 最接近點對問題 最接近點對問題 double cpair2(S) { n=|S|。 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è) ? 習題 28， 29， 210， 227， 230， 231， 232。由于能與p點一起構成最接近點對候選者的 S2中點一定在矩形 R中，所以它們在直線 l上的投影點距 p在 l上投影點的距離小于 d。由圖可以看出， 如果 (md,m]中有 S中的點，則此點就是 S1中最大點。 //找中位數的中位數， rp4即上面所說的 n5 Type x = Select(a, p, p+(rp4)/5, (rp4)/10)。由此可得 T(n)=O(n)。 ji{5, 6, 5, 2, 7, 8} j。 //復制回數組 a } } 復雜度分析 T(n)=O(nlogn) 漸進意義下的最優(yōu)算法 ??????? 11)()2/(2)1()(nnnOnTOnT合并排序 算法 mergeSort的遞歸過程可以消去。} // 覆蓋左下角子棋盤 if (dr = tr + s amp。 棋盤覆蓋 當 k0時，將 2k 2k棋盤分割為 4個 2k1 2k1 子棋盤 (a)所示。因此，在最壞情況下， while循環(huán)被執(zhí)行了O(logn) 次。 分析： 如果 n=1即只有一個元素，則只要比較這個元素和 x就可以確定 x是否在表中。 后兩種方法在時空復雜度上均有較大改善，但其適用范圍有限。 當 n=1時，問題比較簡單。 當最大加數 n1不大于 1時，任何正整數 n只有一種劃分形式， 即 ????? ?nn 111 ???? (4) q(n,m)=q(n,m1)+q(nm,m),nm1。 ? α(n) 在復雜度分析中常遇到。 ? 由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。第 2章 遞歸與分治策略 學習要點 : ? 理解遞歸的概念。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。對于通常所見到的正整數 n，有 α(n)≤4 。 正整數 n的最大加數 n1不大于 m的劃分由 n1=m的劃分和 n1≤n 1 的劃分組成。此時，只要將編號為 1的圓盤從塔座 a直接移至塔座 b上即可。 遞歸小結 分治法的適用條件 分治法所能解決的問題一般具有以下幾個特征： ? 該問題的規(guī)模縮小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有 最優(yōu)子結構性質 ? 利用該問題分解出的子問題的解可以合并為該問題的解； ? 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。因此這個問題滿足分治法的第一個適用條件 分析：