【正文】 用 select來找出這 ?n/5?個元素的中位數(shù)。 return a[p+k1]。 else return Select(a,i+1,r,kj)。最接近點對即為這 n個實數(shù)中相差最小的 2個實數(shù)。 能否在線性時間內(nèi)找到 p3,q3？ 最接近點對問題 ?下面來考慮二維的情形。 ?因此，在分治法的合并步驟中 最多只需要檢查 6 n/2=3n個候選者 能否在線性時間內(nèi)找到 p3,q3？ 證明 :將矩形 R的長為 2d的邊 3等分，將它的長為d的邊 2等分，由此導出 6個 (d/2) (2d/3)的矩形。對 P1中每一點最多只要檢查 P2中排好序的相繼 6個點。 return d。 。 dm=min(d1,d2)。由上面的分析可知，這種投影點最多只有 6個。 滿足這個條件的 P2中的點一定落在一個 d 2d的矩形 R中 ?由 d的意義可知， P2中任何 2個 S中的點的距離都不小于 d。 ?因此，我們用線性時間就能找到區(qū)間 (md,m]和 (m,m+d]中所有點，即 p3和 q3。 ?為了使問題易于理解和分析，先來考慮 一維 的情形。 int i=Partition(a,p,r, x), j=ip+1。而當n≥75時， 3(n5)/10≥n/4所以按此基準劃分所得的 2個子數(shù)組的長度都至少縮短 1/4。 ?將 n個輸入元素劃分成 ?n/5?個組，每組 5個元素，只可能有一個組不是 5個元素。 int i=RandomizedPartition(a,p,r), j=ip+1。 ji{5, 2, 5, 6, 7, 8} i++。 if (i = j) break。 初始序列 [49] [38] [65] [97] [76] [13] [27] [38 49] [65 97] [13 76] [27] 第一步 第二步 [38 49 65 97] [13 27 76] 第三步 [13 27 38 49 65 76 97] 合并排序 ?最壞時間復雜度： O(nlogn) ?平均時間復雜度： O(nlogn) ?輔助空間： O(n) 快速排序 在快速排序中，記錄的比較和交換是從兩端向中間 進行的，關(guān)鍵字較大的記錄一次就能交換到后面單 元，關(guān)鍵字較小的記錄一次就能交換到前面單元， 記錄每次移動的距離較大，因而總的比較和移動次 數(shù)較少。 // 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s)。amp。 else {// 此棋盤中無特殊方格 // 用 t 號 L型骨牌覆蓋右下角 board[tr + s 1][tc + s 1] = t。 特殊方格必位于 4個較小子棋盤之一中，其余 3個子棋盤中無特殊方格。由此可將方程 C=AB重寫為： ?傳統(tǒng)方法 ： O(n3) ?分治法 : ???????????????????222112112221121122211211BBBBAAAACCCC由此可得： 2112111111 BABAC ??2212121112 BABAC ??2122112121 BABAC ??2222122122 BABAC ??復雜度分析 T(n)=O(n3) 22)()2/(7)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : 為了降低時間復雜度，必須減少乘法的次數(shù)。循環(huán)體內(nèi)運算需要 O(1) 時間，因此整個算法在最壞情況下的計算時間復雜性為 O(logn) 。 據(jù)此容易設計出 二分搜索算法 ： templateclass Type int BinarySearch(Type a[], const Typeamp。因此這個問題滿足分治法的第一個適用條件 分析： 比較 x和 a的中間元素 a[mid]，若 x=a[mid]，則 x在 L中的位置就是 mid；如果 xa[mid]，由于 a是遞增排序的，因此假如 x在 a中的話， x必然排在 a[mid]的前面，所以我們只要在a[mid]的前面查找 x即可；如果 xa[i]，同理我們只要在 a[mid]的后面查找 x即可。即將一個問題分成大小相等的 k個子問題的處理方法是行之有效的。 遞歸小結(jié) 分治法的適用條件 分治法所能解決的問題一般具有以下幾個特征： ? 該問題的規(guī)?？s小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) ? 利用該問題分解出的子問題的解可以合并為該問題的解； ? 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 } } 遞歸小結(jié) 優(yōu)點： 結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設計算法、調(diào)試程序帶來很大方便。此時，只要將編號為 1的圓盤從塔座 a直接移至塔座 b上即可?？梢越?q(n,m)的如下遞歸關(guān)系。 正整數(shù) n的最大加數(shù) n1不大于 m的劃分由 n1=m的劃分和 n1≤n 1 的劃分組成。 正整數(shù) n的這種表示稱為正整數(shù) n的劃分。對于通常所見到的正整數(shù) n，有 α(n)≤4 。 } 遞歸的概念 例 3 Ackerman函數(shù) 當一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是 雙遞歸函數(shù) 。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。如果子問題的規(guī)模仍然不夠小，則再劃分為 k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。第 2章 遞歸與分治策略 學習要點 : ? 理解遞歸的概念。 算法總體思想 ? 對這 k個子問題分別求解。 ? 由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。 return fibonacci(n1)+fibonacci(n2)。 ? α(n) 在復雜度分析中常遇到。 遞歸的概念 例 5 整數(shù)劃分問題 將正整數(shù) n表示成一系列正整數(shù)之和： n=n1+n2+… +nk， 其中 n1≥n 2≥ … ≥n k≥1 ， k≥1 。 當最大加數(shù) n1不大于 1時，任何正整數(shù) n只有一種劃分形式， 即 ????? ?nn 111 ???? (4) q(n,m)=q(n,m1)+q(nm,m),nm1。 在本例中，如果設 p(n)為正整數(shù) n的劃分數(shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù) n1不大于 m的劃分個數(shù)記作 q(n,m)。 當 n=1時，問題比較簡單。 hanoi(n1, c, b, a)。 后兩種方法在時空復雜度上均有較大改善，但其適用范圍有限。 //將各子問題的解合并為原問題的解 } 分治法的基本步驟 人們從大量實踐中發(fā)現(xiàn)，在用分治法設計算法時，最好使子問題的規(guī)模大致相同。 分析： 如果 n=1即只有一個元素，則只要比較這個元素和 x就可以確定 x是否在表中。 二分搜索技術(shù) 給定已按升序排好序的 n個元素 a[0:n1]，現(xiàn)要在這 n個元素中找出一特定元素 x。因此，在最壞情況下， while循環(huán)被執(zhí)行了O(logn) 次。因此，算出矩陣 C的 個元素所需的計算時間為 O(n3) ?傳統(tǒng)方法 ： O(n3) Strassen矩陣乘法 使用與上例類似的技術(shù)，將矩陣 A， B和 C中每一矩陣都分塊成 4個大小相等的子矩陣。 棋盤覆蓋 當 k0時，將 2k 2k棋盤分割為 4個 2