【正文】 此基準(zhǔn)劃分所得的 2個(gè)子數(shù)組的長(zhǎng)度都至少縮短 1/4。 private static Comparable select (int p, int r, int k) { if (rp5) { //用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組 a[p:r]排序 。 bubbleSort(p,r)。 return a[p+k1]。 } //將 a[p+5*i]至 a[p+5*i+4]的第 3小元素 //與 a[p+i]交換位置 。 //找中位數(shù)的中位數(shù)， rp4即上面所說(shuō)的 n5 for ( int i = 0。 i=(rp4)/5。 i++ ) { int s=p+5*i, t=s+4。 for (int j=0。j3。j++) bubble(s,tj)。 (a, p+i, s+2)。 } Comparable x = select(p, p+(rp4)/5, (rp+6)/10)。 int i=partition(p,r,x), j=ip+1。 if (k=j) return select(p,i,k)。 else return select(i+1,r,kj)。 } 復(fù)雜度分析 T(n)=O(n) ???????? 7575)4/3()5/()( 21nnnTnTnCCnT上述算法將每一組的大小定為 5，并選取 75作為是否作遞歸調(diào)用的分界點(diǎn)。這 2點(diǎn)保證了 T(n)的遞歸式中 2個(gè)自變量之和n/5+3n/4=19n/20=εn， 0ε1。這是使 T(n)=O(n)的關(guān)鍵之處。當(dāng)然，除了 5和 75之外，還有其他選擇。 最接近點(diǎn)對(duì)問(wèn)題 給定平面上 n個(gè)點(diǎn)的集合 S，找其中的一對(duì)點(diǎn)，使得在 n個(gè)點(diǎn)組成的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)間的距離最小。 ?為了使問(wèn)題易于理解和分析，先來(lái)考慮 一維 的情形。此時(shí)，S中的 n個(gè)點(diǎn)退化為 x軸上的 n個(gè)實(shí)數(shù) x1,x2,…,xn 。最接近點(diǎn)對(duì)即為這 n個(gè)實(shí)數(shù)中相差最小的 2個(gè)實(shí)數(shù)。 ?假設(shè)我們用 x軸上某個(gè)點(diǎn) m將 S劃分為 2個(gè)子集 S1和 S2 ， 基于 平衡子問(wèn)題 的思想，用 S中各點(diǎn)坐標(biāo)的中位數(shù)來(lái)作分割點(diǎn)。 ?遞歸地在 S1和 S2上找出其最接近點(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。 ?能否在線性時(shí)間內(nèi)找到 p3,q3？ 最接近點(diǎn)對(duì)問(wèn)題 ?如果 S的最接近點(diǎn)對(duì)是 {p3,q3}，即 |p3q3|d，則 p3和 q3兩者與 m的距離不超過(guò) d， 即 p3∈ (md,m]， q3∈ (m,m+d]。 ?由于在 S1中，每個(gè)長(zhǎng)度為 d的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于 d），并且 m是 S1和 S2的分割點(diǎn)，因此(md,m]中至多包含 S中的一個(gè)點(diǎn)。由圖可以看出， 如果 (md,m]中有 S中的點(diǎn)，則此點(diǎn)就是 S1中最大點(diǎn)。 ?因此，我們用線性時(shí)間就能找到區(qū)間 (md,m]和 (m,m+d]中所有點(diǎn)，即 p3和 q3。 從而我們用線性時(shí)間就可以將 S1的解和 S2的解合并成為 S的解 。 能否在線性時(shí)間內(nèi)找到 p3,q3？ 最接近點(diǎn)對(duì)問(wèn)題 ?下面來(lái)考慮二維的情形。 ?選取一垂直線 l:x=m來(lái)作為分割直線。其中 m為 S中各點(diǎn) x坐標(biāo)的中位數(shù)。由此將 S分割為 S1和 S2。 ?遞歸地在 S1和 S2上找出其最小距離 d1和 d2，并設(shè)d=min{d1,d2}， S中的最接近點(diǎn)對(duì)或者是 d，或者是某個(gè) {p,q}，其中 p∈ P1且 q∈ P2。 ?能否在線性時(shí)間內(nèi)找到 p,q？ 最接近點(diǎn)對(duì)問(wèn)題 ?考慮 P1中任意一點(diǎn) p，它若與 P2中的點(diǎn) q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有 distance(p， q)＜ d。 滿足這個(gè)條件的 P2中的點(diǎn)一定落在一個(gè) d 2d的矩形 R中 ?由 d的意義可知， P2中任何 2個(gè) S中的點(diǎn)的距離都不小于 d。由此可以推出 矩形 R中最多只有 6個(gè) S中的點(diǎn) 。 ?因此，在分治法的合并步驟中 最多只需要檢查 6 n/2=3n個(gè)候選者 能否在線性時(shí)間內(nèi)找到 p3,q3？ 證明 :將矩形 R的長(zhǎng)為 2d的邊 3等分，將它的長(zhǎng)為d的邊 2等分，由此導(dǎo)出 6個(gè) (d/2) (2d/3)的矩形。若矩形 R中有多于 6個(gè) S中的點(diǎn)，則由鴿舍原理易知至少有一個(gè) (d/2) (2d/3)的小矩形中有 2個(gè)以上 S中的點(diǎn)。設(shè) u， v是位于同一小矩形中的 2個(gè)點(diǎn)，則 distance(u,v)d。這與 d的意義相矛盾。 22222 3625)3/2()2/())()(())()(( dddvyuyvxux ???????為了 確切地知道要檢查哪 6個(gè)點(diǎn) ，可以將 p和P2中所有 S2的點(diǎn)投影到垂直線 l上。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對(duì)候選者的 S2中點(diǎn)一定在矩形 R中，所以它們?cè)谥本€ l上的投影點(diǎn)距 p在 l上投影點(diǎn)的距離小于 d。由上面的分析可知，這種投影點(diǎn)最多只有 6個(gè)。 ?因此，若將 P1和 P2中所有 S中點(diǎn)按其 y坐標(biāo)排好序，則對(duì) P1中所有點(diǎn)，對(duì)排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候選者。對(duì) P1中每一點(diǎn)最多只要檢查 P2中排好序的相繼 6個(gè)點(diǎn)。 最接近點(diǎn)對(duì)問(wèn)題 最接近點(diǎn)對(duì)問(wèn)題 public static double cpair2(S) { n=|S|。 if (n 2) return 。 1. m=S中各點(diǎn) x間坐標(biāo)的中位數(shù) 。 構(gòu)造 S1和 S2； //S1={p∈ S|x(p)=m}, S2={p∈ S|x(p)m} 2. d1=cpair2(S1)。 d2=cpair2(S2)。 3. dm=min(d1,d2)。 4. 設(shè) P1是 S1中距垂直分割線 l的距離在 dm之內(nèi)的所有點(diǎn)組成的集合； P2是 S2中距分割線 l的距離在 dm之內(nèi)所有點(diǎn)組成的集合； 將 P1和 P2中點(diǎn)依其 y坐標(biāo)值排序； 并設(shè) X和 Y是相應(yīng)的已排好序的點(diǎn)列； 5. 通過(guò)掃描 X以及對(duì)于 X中每個(gè)點(diǎn)檢查 Y中與其距離在 dm之內(nèi)的所有點(diǎn) (最多 6個(gè) )可以完成合并； 當(dāng) X中的掃描指針逐次向上移動(dòng)時(shí)， Y中的掃描指針可在寬為 2dm的區(qū)間內(nèi)移動(dòng)； 設(shè) dl是按這種掃描方式找到的點(diǎn)對(duì)間的最小距離； 6. d=min(dm,dl)。 return d。 } 復(fù)雜度分析 T(n)=O(nlogn) ??????? 44)()2/(2)1()(nnnOnTOnT設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他 n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行 n1天。 按分治策略，將所有的選手分為兩半， n個(gè)選手的比賽日程表就可以通過(guò)為 n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這 2個(gè)選手進(jìn)行比賽就可以了。 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 循環(huán)賽日程表 設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他 n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行 n1天。 按分治策略，將所有的選手分為兩半， n個(gè)選手的比賽日程表就可以通過(guò)為 n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這 2個(gè)選手進(jìn)行比賽就可以了。 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