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