【學(xué)習(xí)課件】第2章遞歸與分治策略計(jì)算機(jī)算法設(shè)計(jì)與分析（第3版）教學(xué)

1、第2章 遞歸與分治策略編輯ppt 學(xué)習(xí)要點(diǎn):理解遞歸的概念。掌握設(shè)計(jì)有效算法的分治策略。通過下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。（1）二分搜索技術(shù)； （2）大整數(shù)乘法；（3）Strassen矩陣乘法；（4）棋盤覆蓋；（5）合并排序和快速排序；（6）線性時(shí)間選擇；（7）最接近點(diǎn)對問題；（8）循環(huán)賽日程表。編輯ppt將要求解的較大規(guī)模的問題分割成k個(gè)更小規(guī)模的子問題。算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。編輯ppt算法總體思想對這k個(gè)

2、子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。編輯ppt算法總體思想將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)

3、T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)編輯ppt算法總體思想將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破

4、，分而治之。編輯ppt2.1 遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。下面來看幾個(gè)實(shí)例。編輯ppt2.1 遞歸的概念例1 階乘函數(shù) 階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)

5、算后得出結(jié)果。編輯ppt2.1 遞歸的概念例2 Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int fibonacci(int n) if (n 1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 編輯ppt2.1 遞歸的概念例5 整數(shù)劃分問題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk，其中n1n2nk1，k1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。 例如正整數(shù)6

6、有如下11種不同的劃分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。編輯ppt(2) q(n,m)=q(n,n),mn;最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式，即 (4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1n-1 的劃分組成。(3) q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1n

7、-1的劃分組成。2.1 遞歸的概念例5 整數(shù)劃分問題前面的幾個(gè)例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。編輯ppt2.1 遞歸的概念例5 整數(shù)劃分問題前面的幾個(gè)例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸

8、關(guān)系。正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。 編輯ppt2.1 遞歸的概念例6 Hanoi塔問題設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。編輯ppt在問題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個(gè)問題。當(dāng)n=1時(shí)，問題比較簡單。此時(shí)，

9、只要將編號(hào)為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見，n個(gè)圓盤的移動(dòng)問題可分為2次n-1個(gè)圓盤的移動(dòng)問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計(jì)出解Hanoi塔問題的遞歸算法如下。2.1 遞歸的概念例6 Hanoi塔問題（由a移到b） void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move

10、(a,b); hanoi(n-1, c, b, a); 編輯ppt遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。編輯ppt解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實(shí)現(xiàn)遞歸函數(shù)。3、通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其

11、適用范圍有限。遞歸小結(jié)編輯ppt遞推植樹節(jié)那天，有五位同學(xué)參加了植樹活動(dòng)，他們完成植樹的棵樹都不相同。問第一位同學(xué)植了多少棵時(shí)，他指著旁邊的第二位同學(xué)說比他多植了兩棵；追問第二位同學(xué)，他又說比第三位同學(xué)多植了兩棵；. 如此，都說比另一位同學(xué)多植兩棵。最后問到第五位同學(xué)時(shí)，他說自己植了10棵。到底第一位同學(xué)植了多少棵樹？ 編輯ppt遞推分析：設(shè)第一位同學(xué)植樹的棵樹為a1,欲求a1，需從第五位同學(xué)植樹的棵數(shù)a5入手，根據(jù)“多兩棵”這個(gè)規(guī)律，按照一定順序逐步進(jìn)行推算： (1) a5=10; (2) a4=a5+2=12; (3) a3=a4+2=14; (4) a2=a3+2=16; (5) a1=

12、a2+2=18; 編輯ppt尾遞歸線性遞歸: long Rescuvie(long n) return(n = 1) ? 1 : n * Rescuvie(n - 1); 尾遞歸: long TailRescuvie(long n, long a) return(n = 1) ? a : TailRescuvie(n - 1, a * n); long TailRescuvie(long n) /封裝用的 return(n = 0) ? 1 : TailRescuvie(n, 1); 編輯ppt尾遞歸當(dāng)n = 5時(shí) 對于線性遞歸, 他的遞歸過程如下: Rescuvie(5) 5 * Rescu

13、vie(4) 5 * 4 * Rescuvie(3) 5 * 4 * 3 * Rescuvie(2) 5 * 4 * 3 * 2 * Rescuvie(1) 5 * 4 * 3 * 2 * 1 5 * 4 * 3 * 2 5 * 4 * 6 5 * 24 120 編輯ppt尾遞歸對于尾遞歸, 他的遞歸過程如下: TailRescuvie(5) TailRescuvie(5, 1) TailRescuvie(4, 5) TailRescuvie(3, 20) TailRescuvie(2, 60) TailRescuvie(1, 120) 120 編輯ppt分治法的適用條件分治法所能解決的問題一

14、般具有以下幾個(gè)特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。 因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個(gè)特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要

15、做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。編輯pptdivide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問題 else divide P into smaller subinstances P1,P2,.,Pk；/分解問題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問題 return merge(y1,.,yk); /將各子問題的解合并為原問題的解 分治法的基本步驟人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相

16、同。即將一個(gè)問題分成大小相等的k個(gè)子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。編輯ppt分治法的復(fù)雜性分析一個(gè)分治法將規(guī)模為n的問題分成k個(gè)規(guī)模為nm的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問題分解為k個(gè)子問題以及用merge將k個(gè)子問題的解合并為原問題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間，則有：通過迭代法求得方程的解：編輯ppt分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定

17、x是否在表中。因此這個(gè)問題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個(gè)和第三個(gè)適用條件。 分析：很顯然此問題分解出的子問題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問題，因此滿足分治法的第四個(gè)適用條件。二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。分析：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個(gè)

18、規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個(gè)子問題是相互獨(dú)立的。 編輯ppt二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。據(jù)此容易設(shè)計(jì)出二分搜索算法：template int BinarySearch(Type a, const Type& x, int l, int r) while (r = l) int m = (l+r)/2; if (x = am) return m; if (x am) r = m-1; else l = m+1; return -1; 算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)

19、組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。編輯ppt大整數(shù)的乘法 請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2) 效率太低分治法: X = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd abcd復(fù)雜度分析T(n)=O(n2) 沒有改進(jìn)編輯ppt大整數(shù)的乘法 請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2) 效率太低分治法: X

20、Y = ac 2n + (ad+bc) 2n/2 + bd 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。XY = ac 2n + (a-b)(d-c)+ac+bd) 2n/2 + bd復(fù)雜度分析T(n)=O(nlog3) =O(n1.59)較大的改進(jìn)編輯ppt大整數(shù)的乘法 請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2) 效率太低分治法: O(n1.59) 較大的改進(jìn)更快的方法?如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個(gè)思想導(dǎo)致了快速傅利葉變換(Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個(gè)復(fù)

21、雜的分治算法。編輯pptStrassen矩陣乘法A和B的乘積矩陣C中的元素Ci,j定義為: 若依此定義來計(jì)算A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素Cij，需要做n次乘法和n-1次加法。因此，算出矩陣C的所有元素所需的計(jì)算時(shí)間為O(n3)傳統(tǒng)方法：O(n3)編輯pptStrassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣。由此可將方程C=AB重寫為：傳統(tǒng)方法：O(n3)分治法:由此可得：復(fù)雜度分析T(n)=O(n3)編輯pptStrassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。復(fù)雜度分析T(n)=O(nlog

22、7) =O(n2.81)較大的改進(jìn)編輯pptStrassen矩陣乘法傳統(tǒng)方法：O(n3)分治法: O(n2.81)更快的方法?Hopcroft和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算22矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究或矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。目前最好的計(jì)算時(shí)間上界是 O(n2.376)是否能找到O(n2)的算法？編輯ppt合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求

23、的排好序的集合。 void MergeSort(Type a, int left, int right) if (leftright) /至少有2個(gè)元素 int i=(left+right)/2; /取中點(diǎn) mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); /合并到數(shù)組b copy(a, b, left, right); /復(fù)制回?cái)?shù)組a 復(fù)雜度分析T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法編輯ppt合并排序（合并算法見P22）算法mergeSort的遞歸過程可以消去。初始序列49 3

24、8 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97編輯ppt合并排序最壞時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)編輯ppt快速排序在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Part

25、ition(a,p,r); QuickSort (a,p,q-1); /對左半段排序 QuickSort (a,q+1,r); /對右半段排序 編輯ppt快速排序templateint Partition (Type a, int p, int r) int i = p, j = r + 1; Type x=ap; / 將 x的元素交換到右邊區(qū)域 while (true) while (a+i x); if (i = j) break; Swap(ai, aj); ap = aj; aj = x; return j;初始序列6, 7, 5, 2, 5, 8j-;5, 7, 5, 2, 6, 8

26、i+;5, 6, 5, 2, 7, 8j-;5, 2, 5, 6, 7, 8i+;完成6, 7, 5, 2, 5, 85, 2, 5 6 7, 8編輯ppttemplateint RandomizedPartition (Type a, int p, int r) int i = Random(p,r); Swap(ai, ap); return Partition (a, p, r);快速排序 快速排序算法的性能取決于劃分的對稱性。通過修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分

27、基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對稱的。最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)或O(logn)編輯ppt最接近點(diǎn)對問題給定平面上n個(gè)點(diǎn)的集合S，找其中的一對點(diǎn)，使得在n個(gè)點(diǎn)組成的所有點(diǎn)對中，該點(diǎn)對間的距離最小。 為了使問題易于理解和分析，先來考慮一維的情形。此時(shí)，S中的n個(gè)點(diǎn)退化為x軸上的n個(gè)實(shí)數(shù) x1,x2,xn。最接近點(diǎn)對即為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。假設(shè)我們用x軸上某個(gè)點(diǎn)m將S劃分為2個(gè)子集S1和S2 ，基于平衡子問題的思想，用S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。遞歸地在S1和S2上找出其最接近點(diǎn)對p1,p2和q1,q2

28、，并設(shè)d=min|p1-p2|,|q1-q2|，S中的最接近點(diǎn)對或者是p1,p2，或者是q1,q2，或者是某個(gè)p3,q3，其中p3S1且q3S2。能否在線性時(shí)間內(nèi)找到p3,q3？編輯ppt最接近點(diǎn)對問題如果S的最接近點(diǎn)對是p3,q3，即|p3-q3|d，則p3和q3兩者與m的距離不超過d，即p3(m-d,m，q3(m,m+d。由于在S1中，每個(gè)長度為d的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于d），并且m是S1和S2的分割點(diǎn)，因此(m-d,m中至多包含S中的一個(gè)點(diǎn)。由圖可以看出，如果(m-d,m中有S中的點(diǎn)，則此點(diǎn)就是S1中最大點(diǎn)。因此，我們用線性時(shí)間就能找到區(qū)間(m-d,m和(m,m+d

29、中所有點(diǎn)，即p3和q3。從而我們用線性時(shí)間就可以將S1的解和S2的解合并成為S的解。能否在線性時(shí)間內(nèi)找到p3,q3？編輯ppt最接近點(diǎn)對問題下面來考慮二維的情形。選取一垂直線l:x=m來作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=mind1,d2，S中的最接近點(diǎn)對或者是d，或者是某個(gè)p,q，其中pP1且qP2。能否在線性時(shí)間內(nèi)找到p,q？編輯ppt最接近點(diǎn)對問題考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對的候選者，則必有distance(p，q)d。滿足這個(gè)條件的P2中的點(diǎn)一定落在一個(gè)d2d的矩形R中由d的意義可知，P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由此可以推出矩形R中最多只有6個(gè)S中的點(diǎn)。因此，在分治法的合并步驟中最多只需要檢查6n/2=3n個(gè)候選者能否在線性時(shí)間內(nèi)找到p3,q3？證明:將矩形R的長為2d的邊3等分，將它的長為d的邊2等分，由此導(dǎo)出6個(gè)(d/2)(2d/3)的