王曉東《算法設(shè)計(jì)與分析》課件

1、1 中國(guó)計(jì)算機(jī)學(xué)會(huì)中國(guó)計(jì)算機(jī)學(xué)會(huì) “21“21世紀(jì)大學(xué)本科計(jì)算機(jī)專業(yè)系列教材世紀(jì)大學(xué)本科計(jì)算機(jī)專業(yè)系列教材” 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 王曉東王曉東編著編著 2 主要內(nèi)容介紹主要內(nèi)容介紹 第1章算法引論 第2章遞歸與分治策略 第3章動(dòng)態(tài)規(guī)劃 第4章貪心算法 第5章回溯法 第6章分支限界法 3 主要內(nèi)容介紹（續(xù)）主要內(nèi)容介紹（續(xù)） 第7章概率算法 第8章NP完全性理論 第9章近似算法 第10章 算法優(yōu)化策略 4 第第1 1章章 算法引論算法引論 1.1 算法與程序 1.2 表達(dá)算法的抽象機(jī)制 1.3 描述算法 1.4 算法復(fù)雜性分析 本章主要知識(shí)點(diǎn)： 5 1.1 算法與程序算法與程序 輸 入

2、：有零個(gè)或多個(gè)外部量作為算法的輸入。 輸 出：算法產(chǎn)生至少一個(gè)量作為輸出。 確定性：組成算法的每條指令清晰、無(wú)歧義。 有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行 每條指令的時(shí)間也有限。 是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。 程序可以不滿足算法的性質(zhì)(4)即有限性。 是滿足下述性質(zhì)的指令序列。算法： 程序： 6 1.從機(jī)器語(yǔ)言到高級(jí)語(yǔ)言的抽象 1.2 表達(dá)算法的抽象機(jī)制表達(dá)算法的抽象機(jī)制 高級(jí)程序設(shè)計(jì)語(yǔ)言的主要好處是： （4）把繁雜瑣碎的事務(wù)交給編譯程序，所以自動(dòng)化程度高，開(kāi)發(fā)周期短， 程序員可以集中時(shí)間和精力從事更重要的創(chuàng)造性勞動(dòng)，提高程序質(zhì)量。 （1）高級(jí)語(yǔ)言更接近算法語(yǔ)言，易學(xué)、易掌握，一

3、般工程技術(shù)人員只需 要幾周時(shí)間的培訓(xùn)就可以勝任程序員的工作； （2）高級(jí)語(yǔ)言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì) 出來(lái)的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高； （3）高級(jí)語(yǔ)言不依賴于機(jī)器語(yǔ)言，與具體的計(jì)算機(jī)硬件關(guān)系不大，因而 所寫出來(lái)的程序可植性好、重用率高； 7 2.抽象數(shù)據(jù)類型 1.2 表達(dá)算法的抽象機(jī)制表達(dá)算法的抽象機(jī)制 抽象數(shù)據(jù)類型是算法的一個(gè)數(shù)據(jù)模型連同定義在該模型上 并作為算法構(gòu)件的一組運(yùn)算。 抽象數(shù)據(jù)類型帶給算法設(shè)計(jì)的好處有： （1）算法頂層設(shè)計(jì)與底層實(shí)現(xiàn)分離； （2）算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)隔開(kāi)，允許數(shù)據(jù)結(jié)構(gòu)自由選擇； （3）數(shù)據(jù)模型和該模型上的運(yùn)算統(tǒng)一在ADT中，便

4、于空間和時(shí)間耗費(fèi)的折衷； （4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維護(hù)性； （5）算法自然呈現(xiàn)模塊化； （6）為自頂向下逐步求精和模塊化提供有效途徑和工具； （7）算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜性的分析。 8 在本書中，采用Java語(yǔ)言描述算法。 1.1.JavaJava程序結(jié)構(gòu)程序結(jié)構(gòu) 1.3 描述算法描述算法 以下，對(duì)JavaJava語(yǔ)言的若干重要特性作簡(jiǎn)要概述。 （1）Java程序的兩種類型：應(yīng)用程序和appletapplet 區(qū)別：應(yīng)用程序的主方法為main，其可在命令行中用命令 語(yǔ)句 java 應(yīng)用程序名 來(lái)執(zhí)行； applet的主方法為init，其必須嵌入HT

5、ML文件，由 Web瀏覽器或applet閱讀器來(lái)執(zhí)行。 （2）包：java程序和類可以包(packages)的形式組織管理。 （3）import語(yǔ)句：在java程序中可用import語(yǔ)句加載所需的包。 例如，import java.io.*;語(yǔ)句加載java.io包。 9 1.3 描述算法描述算法 2.2.JavaJava數(shù)據(jù)類型數(shù)據(jù)類型 數(shù)據(jù)類型 基本數(shù)據(jù)類型：詳見(jiàn)下頁(yè)表1-1 非基本數(shù)據(jù)類型：如 Byte, Integer, Boolean, String等。 Java對(duì)兩種數(shù)據(jù)類型的不同處理方式： 對(duì)基本數(shù)據(jù)類型：在聲明一個(gè)具有基本數(shù)據(jù)類型的變量時(shí)，自 動(dòng)建立該數(shù)據(jù)類型的對(duì)象（或稱實(shí)例）

6、。如:int k; 對(duì)非基本數(shù)據(jù)類型：語(yǔ)句 String s; 并不建立具有數(shù)據(jù)類型 String的對(duì)象，而是建立一個(gè)類型String的引用對(duì)象， 數(shù)據(jù)類型為String的對(duì)象可用下面的new語(yǔ)句建立。 s = new StringString(“Welcome”); StringString s = new StringString(“Welcome”); 10 1.3 描述算法描述算法 表格表格1-1 1-1 JavaJava基本數(shù)據(jù)類型基本數(shù)據(jù)類型 類型缺省值分配空間（bits）取值范圍 booleanfalse1true,false byte08-128,127 charu000016

7、u0000,uFFFF double0.0644.9*10-324 1.8*10308 float0.0321.4*10-45 3.4*1038 int032-2147483648,2147483647 long0649.2*1017 short016-32768,32767 11 1.3 描述算法描述算法 3.3.方法方法 在Java中，執(zhí)行特定任務(wù)的函數(shù)或過(guò)程統(tǒng)稱為方法(methods) 。 例如，java的MathMath類類給出的常見(jiàn)數(shù)學(xué)計(jì)算的方法如下表所示： 方法方法功能功能方法方法功能功能 abs(x)x的絕對(duì)值max(x,y)x和y中較大者 ceil(x)不小于x的最小整數(shù)min

8、(x,y)x和y中較小者 cos(x)x的余弦pow(x,y)xy exp(x)exsin(x)x的正弦 floor(x)不大于x的最大整數(shù)sqrt(x)x的平方根 log(x)x的自然對(duì)數(shù)tan(x)x的正切 12 1.3 描述算法描述算法 3.3.方法方法 2 baba 計(jì)算表達(dá)式 值的自定義方法ab描述如下： public static int ab(int a, int b) return (a+b+Math.abs(a-b)/2; （1）方法參數(shù)：Java中所有方法的參數(shù)均為值參數(shù)。上述方法ab中，a和b 是形式參數(shù)，在調(diào)用方法時(shí)通過(guò)實(shí)際參數(shù)賦值。 （2）方法重載：Java允許方法重

9、載，即允許定義有不同簽名的同名方法。 上述方法ab可重載為： public static double ab(double a, double b) return (a+b+Math.abs(a-b)/2.0; 13 1.3 描述算法描述算法 4.4.異常異常 Java的異常提供了一種處理錯(cuò)誤的方法。當(dāng)程序發(fā)現(xiàn)一個(gè) 錯(cuò)誤，就引發(fā)一個(gè)異常，以便在合適地方捕獲異常并進(jìn)行處理。 通常用trytry塊來(lái)定義異常處理。每個(gè)異常處理由一個(gè)catchcatch 語(yǔ)句組成。 public static void main(String args) try f ( ); catch (exception1) 異

10、常處理; catch (exception2) 異常處理; finally finally塊; 14 1.3 描述算法描述算法 5.5.JavaJava的類的類 (4)訪問(wèn)修飾訪問(wèn)修飾 公有(public) 私有(private) 保護(hù)(protected) Java的類一般由4個(gè)部分組成： (1)類名類名 (2)數(shù)據(jù)成員數(shù)據(jù)成員 (3)方法方法 15 1.3 描述算法描述算法 6.6.通用方法通用方法 下面的方法swapswap用于交換一維整型數(shù)組a的位置i和位置j處的值。 public static void swap(int a, int i, int j) int temp = ai;

11、 ai = aj; aj = temp; public static void swap(object a, int i, int j) object temp = ai; ai = aj; aj = temp; 該方法只適用于該方法只適用于 整型數(shù)組整型數(shù)組 該方法具有通用性，適用該方法具有通用性，適用 于于ObjectObject類型及其所有子類型及其所有子 類類 以上方法修改如下：以上方法修改如下： 16 1.3描述算法描述算法 6.6.通用方法通用方法 （1 1）ComputableComputable界面界面 public static Computable sum(Computab

12、le a, int n) if (a.length = 0) return null; Computable sum = (Computable) a0.zero(); for (int i = 0; i n; i+) sum.increment(ai); return sum; 利用此界面使利用此界面使 方法方法sumsum通用化通用化 17 1.3 描述算法描述算法 6.6.通用方法通用方法 （2 2）java.lang.Comparable java.lang.Comparable 界面界面 Java的Comparable 界面中惟一的方法頭compareTo用于比較 2個(gè)元素的大小。例

13、如java.lang.CpareTo(y) 返回x-y的符號(hào)，當(dāng)xy時(shí)返 回正數(shù)。 （3 3）OperableOperable 界面界面 有些通用方法同時(shí)需要Computable界面和Comparable 界面 的支持。為此可定義Operable界面如下: public interface Operable extends Computable, Comparable （4 4）自定義包裝類）自定義包裝類 由于Java的包裝類如Integer等已定義為final型，因此無(wú)法 定義其子類，作進(jìn)一步擴(kuò)充。為了需要可自定義包裝類。 18 1.3 描述算法描述算法 7.7.垃圾收集垃圾收集 8.8.遞

14、歸遞歸 Java的newnew運(yùn)算用于分配所需的內(nèi)存空間。 例如， int a = new int500000; 分配2000000字節(jié)空間 給整型數(shù)組a。頻繁用new分配空間可能會(huì)耗盡內(nèi)存。Java的垃垃 圾收集器圾收集器會(huì)適時(shí)掃描內(nèi)存，回收不用的空間（垃圾）給new重新 分配。 Java允許方法調(diào)用其自身。這類方法稱為遞歸方法。 public static int sum(int a, int n) if (n=0) return 0; else return an-1+sum(a,n-1); 計(jì)算一維整型數(shù)組前計(jì)算一維整型數(shù)組前n n個(gè)個(gè) 元素之和的遞歸方法元素之和的遞歸方法 19 1.

15、4 算法復(fù)雜性分析算法復(fù)雜性分析 算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量， 需要時(shí)間資源的量稱為時(shí)間復(fù)雜性時(shí)間復(fù)雜性，需要的空間資源的 量稱為空間復(fù)雜性空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問(wèn) 題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用 N、I和A表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法 本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。 一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開(kāi)，并分別用T和S來(lái) 表示，則有： T=T(N,I)和S=S(N,I) 。 （通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中） 20 1.4 算法復(fù)雜性分析算法復(fù)雜性分析 最壞情況下的時(shí)間復(fù)雜性： ),(max max

16、INT(N)T N DI ),(max 1 INet k i ii DI N ),( * 1 INet k i ii ),( * INT 最好情況下的時(shí)間復(fù)雜性： ),(min min INT(N)T N DI ),(min 1 INet k i ii DI N ) ,( 1 INet k i ii ) ,(INT 平均情況下的時(shí)間復(fù)雜性： N DI INTIP(N)T),()( avg N DI k i ii INetIP),()( 1 其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N, I*) 達(dá)到Tmax(N)的合法輸入； 是中使T(N, )達(dá)到Tmin(N)的合法 輸入；而P(

17、I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。 I I 21 1.4 算法復(fù)雜性分析算法復(fù)雜性分析 算法復(fù)雜性在漸近意義下的階： 漸近意義下的記號(hào)：O、o 設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。 O O的定義的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有 f(N)Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一 個(gè)上界，記為f(N)=O(g(N)。即f(N)的階不高于g(N)的階。 根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則： (1)O(f)+O(g)=O(max(f,g)； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)； (4)如果g(

18、N)=O(f(N)，則O(f)+O(g)=O(f)； (5)O(Cf(N)=O(f(N)，其中C是一個(gè)正的常數(shù)； (6)f=O(f)。 22 1.4 算法復(fù)雜性分析算法復(fù)雜性分析 的定義的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí) 有f(N)Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)下有界，且g(N)是它 的一個(gè)下界，記為f(N)=(g(N)。即f(N)的階不低于g(N)的階。 的定義的定義：定義f(N)= (g(N)當(dāng)且僅當(dāng)f(N)=O(g(N)且 f(N)= (g(N)。此時(shí)稱f(N)與g(N)同階。 o o的定義的定義：對(duì)于任意給定的0，都存在正整數(shù)N0，使得 當(dāng)NN0時(shí)有f(N

19、)/Cg(N),則稱函數(shù)f(N)當(dāng)N充分大時(shí)的階比 g(N)低，記為f(N)=o(g(N)。 例如，4NlogN+7=o(3N2+4NlogN+7)。 23 24 將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn) 題。 n T(n/2) T(n/2)T(n/2)T(n/2) T(n) = 對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠 小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直 到問(wèn)題規(guī)模足夠小，很容易求出其解為止。 25 對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠 小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直 到問(wèn)題規(guī)模足夠小，很容易求出其解為止。 n T(n) = n/2

20、 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ī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn) 題的解，自底向上逐步求出原來(lái)問(wèn)題的解。 26 將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn) 題的解，自底向上逐步求出原來(lái)問(wè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)

21、n/2 T(n/4)T(n/4)T(n/4)T(n/4) 27 將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn) 題的解，自底向上逐步求出原來(lái)問(wè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)題，分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題， 分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破， 分而治之。

22、分而治之。 凡治眾如治寡，分?jǐn)?shù)是也。凡治眾如治寡，分?jǐn)?shù)是也。 -孫子兵法孫子兵法 28 2.1 2.1 直接或間接地調(diào)用自身的算法稱為遞歸算法遞歸算法。 用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)遞歸函數(shù)。 由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模 式，這就為使用遞歸技術(shù)提供了方便。在這種 情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與 原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使 子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo) 致遞歸過(guò)程的產(chǎn)生。 分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在 算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。 下面來(lái)看幾個(gè)實(shí)例。 29 2.1 2.1 例例1 1 階乘函數(shù)階乘函數(shù) 階乘函數(shù)可遞歸

23、地定義為： 0 0 )!1( 1 ! n n nn n 邊界條件邊界條件 遞歸方程遞歸方程 邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函 數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出 結(jié)果。 30 2.1 2.1 例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列 無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，被 稱為Fibonacci數(shù)列。它可以遞歸地定義為： 邊界條件邊界條件 遞歸方程遞歸方程 1 1 0 )2() 1( 1 1 )( n n n nFnF nF 第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下： public static int fibonacci(int

24、 n) if (n 1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)， (rn)perm(Rn)構(gòu)成。 37 2.1 2.1 例例5 5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題 將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk， 其中n1n2nk1，k1。 正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不 同劃分個(gè)數(shù)。 例如正整數(shù)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。 38 (2) q(n,m)=q(n,n),mn; 最大加數(shù)n1實(shí)際上

25、不能大于n。因此，q(1,m)=1。 (1) q(n,1)=1,n1; 當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式， 即 n n111 (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-1的劃分組成。 2.1 2.1 例例5 5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題 前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因 而容易用遞歸函數(shù)直接求解。 在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)

26、系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè) 數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。 39 1 1, 1 ),() 1,( ) 1,(1 ),( 1 ),( mn mn mn mn mmnqmnq nnq nnq mnq 2.1 2.1 例例5 5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題 前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(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)系。 正整數(shù)n的劃分?jǐn)?shù)p(n)=q

27、(n,n)。 40 41 2.1 2.1 例例6 Hanoi6 Hanoi塔問(wèn)題塔問(wèn)題 設(shè)a,b,c是3個(gè)塔座。開(kāi)始時(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中任一塔座上。 42 在問(wèn)題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試 用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)題。 當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)

28、單。此時(shí)，只要將編號(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。 由此可見(jiàn)，n個(gè)圓盤的移動(dòng)問(wèn)題可分為2次n-1個(gè)圓盤的移動(dòng)問(wèn)題， 這又可以遞歸地用上述方法來(lái)做。由此可以設(shè)計(jì)出解Hanoi塔問(wèn)題 的遞歸算法如下。 2.1 2.1 例例6 6 HanoiHanoi塔問(wèn)題塔問(wèn)題 public static void hanoi(int n, int a, int b, int c) if

29、(n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 43 優(yōu)點(diǎn)：優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸 納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、 調(diào)試程序帶來(lái)很大方便。調(diào)試程序帶來(lái)很大方便。 缺點(diǎn)：缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的 計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法 要多。要多。 44 解決方法：解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)在遞歸算法中消除遞

30、歸調(diào)用，使其轉(zhuǎn) 化為非遞歸算法?；癁榉沁f歸算法。 1.1.采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用 工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸， 只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化 效果不明顯。效果不明顯。 2.2.用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。 3.3.通過(guò)通過(guò)CooperCooper變換、變換、反演變換能反演變換能將一些遞歸轉(zhuǎn)化將一些遞歸轉(zhuǎn)化 為尾遞歸，從而迭代求出結(jié)果。為尾遞歸，從而迭代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善，后兩種方法在時(shí)

31、空復(fù)雜度上均有較大改善， 但其適用范圍有限。但其適用范圍有限。 45 該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決； 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該 問(wèn)題具有問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的 解；解； 該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn) 題之間不包含公共的子問(wèn)題。題之間不包含公共的子問(wèn)題。 因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加

32、 而增加，因此大部分問(wèn)題滿足這個(gè)特征。 這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題 可以滿足的，此特征反映了遞歸思想的應(yīng)用 能否利用分治法完全取決于問(wèn)題是否具有這條特征， 如果具備了前兩條特征，而不具備第三條特征，則 可以考慮貪心算法貪心算法或動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃。 這條特征涉及到分治法的效率，如果各子問(wèn)題是不 獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地 解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般 用動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃較好。 46 divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問(wèn)題 divide P into smaller s

33、ubinstances P1,P2,.,Pk；/分解問(wèn)題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問(wèn)題 return merge(y1,.,yk); /將各子問(wèn)題的解合并為原問(wèn)題的解 人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使 子問(wèn)題的規(guī)模大致相同。即將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn) 題的處理方法是行之有效的。這種使子問(wèn)題規(guī)模大致相等的做 法是出自一種平衡平衡(balancing)子問(wèn)題子問(wèn)題的思想，它幾乎總是比子 問(wèn)題規(guī)模不等的做法要好。 47 一個(gè)分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為nm的子問(wèn)題去解。 設(shè)分解閥值n0=1

34、，且adhoc解規(guī)模為1的問(wèn)題耗費(fèi)1個(gè)單位時(shí)間。 再設(shè)將原問(wèn)題分解為k個(gè)子問(wèn)題以及用merge將k個(gè)子問(wèn)題的解合 并為原問(wèn)題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解 規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間，則有： 1 1 )()/( ) 1 ( )( n n nfmnkT O nT 通過(guò)迭代法求得方程的解： 1log 0 log )/()( n m j jj k m mnfknnT 注意注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但 是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值 可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而 當(dāng)minmi

35、+1時(shí)，T(mi)T(n)T(mi+1)。 48 分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就 可以確定x是否在表中。因此這個(gè)問(wèn)題滿足分治法的第一個(gè)適 用條件 分析：比較x和a的中間元素amid，若x=amid，則x在L中的 位置就是mid；如果xai，同理我們只要在amid 的后面查找x即可。無(wú)論是在前面還是后面查找x，其方法都 和在a中查找x一樣，只不過(guò)是查找的規(guī)?？s小了。這就說(shuō)明 了此問(wèn)題滿足分治法的第二個(gè)和第三個(gè)適用條件。 分析：很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在ai的前 面或后面查找x是獨(dú)立的子問(wèn)題，因此滿足分治法的第四個(gè)適 用條件。 給定已按升序排好序的給定已按升

36、序排好序的n個(gè)元素個(gè)元素a0:n-1，現(xiàn)要在這現(xiàn)要在這n個(gè)元素中找個(gè)元素中找 出一特定元素出一特定元素x。 分析：分析： 該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決； 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題; 分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的子問(wèn)題的解可以合并為原問(wèn)題的解； 分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。 49 給定已按升序排好序的給定已按升序排好序的n個(gè)元素個(gè)元素a0:n-1，現(xiàn)要在這現(xiàn)要在這n個(gè)元素中找個(gè)元素中找 出一特定元素出一特定元素x。 據(jù)此容易

37、設(shè)計(jì)出二分搜索算法二分搜索算法： public static int binarySearch(int a, int x, int n) / 在 a0 = a1 = . = an-1 中搜索 x / 找到x時(shí)返回其在數(shù)組中的位置，否則返回-1 int left = 0; int right = n - 1; while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 算法復(fù)雜度分析：算法復(fù)雜度分析： 每執(zhí)行一次算法的 while循環(huán)， 待搜索數(shù) 組的大小減少一半。因 此，在最壞情況下， w

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

39、設(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n n位大整數(shù)的乘法運(yùn)算位大整數(shù)的乘法運(yùn)算 u小學(xué)的方法：O(n2) 效率太低 u分治法: XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。 1. XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bd 2. XY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd 復(fù)雜度分析復(fù)雜度分析 T(n)=O(nlog3) =O(n1.59) 較大的改進(jìn)較大的改進(jìn) 1 1 )()2/(3 ) 1 ( )( n n nOnT O nT

40、細(xì)節(jié)問(wèn)題細(xì)節(jié)問(wèn)題：兩個(gè)XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可 能得到m+1位的結(jié)果，使問(wèn)題的規(guī)模變大，故不選擇第2種方案。 52 請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n n位大整數(shù)的乘法運(yùn)算位大整數(shù)的乘法運(yùn)算 u小學(xué)的方法：O(n2) 效率太低 u分治法: O(n1.59) 較大的改進(jìn) u更快的方法? 如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來(lái)， 將有可能得到更優(yōu)的算法。 最終的，這個(gè)思想導(dǎo)致了快速傅利葉變換快速傅利葉變換(Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個(gè)復(fù)雜的分治算 法，對(duì)于大整數(shù)乘法，

41、它能在O(nlogn)時(shí)間內(nèi)解決。 是否能找到線性時(shí)間的算法？目前為止還沒(méi)有結(jié)果。 53 A和B的乘積矩陣C中的元素Ci,j定義為: n k jkBkiAjiC 1 若依此定義來(lái)計(jì)算A和B的乘積矩陣C，則每計(jì) 算C的一個(gè)元素Cij，需要做n次乘法和n-1次 加法。因此，算出矩陣C的 個(gè)元素所需的計(jì)算 時(shí)間為O(n3) u傳統(tǒng)方法：O(n3) 54 使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4 個(gè)大小相等的子矩陣。由此可將方程C=AB重寫為： u傳統(tǒng)方法：O(n3) u分治法: 2221 1211 2221 1211 2221 1211 BB BB AA AA CC CC 由此可得

42、： 2112111111 BABAC 2212121112 BABAC 2122112121 BABAC 2222122122 BABAC 復(fù)雜度分析復(fù)雜度分析 T(n)=O(n3) 沒(méi)有改進(jìn)沒(méi)有改進(jìn) 2 2 )()2/(7 ) 1 ( )( 2 n n nOnT O nT 55 u傳統(tǒng)方法：O(n3) u分治法: 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。 2221 1211 2221 1211 2221 1211 BB BB AA AA CC CC )( 2212111 BBAM 2212112 )(BAAM 1122213 )(BAAM )( 1121224 BBAM )( 2211221

43、15 BBAAM )( 222122126 BBAAM )( 121121117 BBAAM 624511 MMMMC 2112 MMC 4321 MMC 731522 MMMMC 復(fù)雜度分析復(fù)雜度分析 T(n)=O(nlog7) =O(n2.81) 較大的改進(jìn)較大的改進(jìn) 2 2 )()2/(8 ) 1 ( )( 2 n n nOnT O nT 56 u傳統(tǒng)方法：O(n3) u分治法: O(n2.81) u更快的方法? Hopcroft和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)矩陣的乘 積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí) 間復(fù)雜性，就不能再基于計(jì)算22矩陣的7次乘法這樣的方法

44、 了?；蛟S應(yīng)當(dāng)研究或矩陣的更好算法。 在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù) 雜性。目前最好的計(jì)算時(shí)間上界是 O(n2.376) 是否能找到O(n2)的算法？目前為止還沒(méi)有結(jié)果。 57 在一個(gè)2k2k 個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他方格 不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在 棋盤覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定 的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌 不得重疊覆蓋。 58 當(dāng)k0時(shí)，將2k2k棋盤分割為4個(gè)2k-12k-1 子棋盤(a)所示。 特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無(wú)特 殊方格。

45、為了將這3個(gè)無(wú)特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可 以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，如 (b)所示， 從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題。遞歸地使用 這種分割，直至棋盤簡(jiǎn)化為棋盤11。 59 public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌號(hào) s = size/2; / 分割棋盤 / 覆蓋左上角子棋盤 if (dr tr + s else / 此棋盤中無(wú)特殊方格 / 用 t 號(hào)L型骨牌覆蓋右下角 boardt

46、r + s - 1tc + s - 1 = t; / 覆蓋其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆蓋右上角子棋盤 if (dr = tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤中無(wú)特殊方格 / 用 t 號(hào)L型骨牌覆蓋左下角 boardtr + s - 1tc + s = t; / 覆蓋其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆蓋左下角子棋盤 if (dr = tr + s else / 用 t 號(hào)L型骨牌覆蓋

47、左上角 boardtr + stc + s = t; / 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 復(fù)雜度分析復(fù)雜度分析 T(n)=O(4k) 漸進(jìn)意義下的最優(yōu)算法 0 0 ) 1 () 1(4 ) 1 ( )( k k OkT O kT 60 基本思想：基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分 別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所 要求的排好序的集合。 public static void mergeSort(Comparable a, int left, int right) if (leftright) /

48、至少有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ù)雜度分析復(fù)雜度分析 T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法 1 1 )()2/(2 ) 1 ( )( n n nOnT O nT 61 算法mergeSort的遞歸過(guò)程可以消去。 初始序列49 38 65 97 76 13 27 38 49 65 97 13 76 27 第一步

49、第二步38 49 65 97 13 27 76 第三步 13 27 38 49 65 76 97 62 if (i = j) break; MyMath.swap(a, i, j); ap = aj; aj = x; return j; 初始序列 6, 7, 5, 2, 5, 8 j-; j i 5, 7, 5, 2, 6, 8 i+; ji 5, 6, 5, 2, 7, 8 j-; j i 5, 2, 5, 6, 7, 8 i+; ji 完成 快速排序具有不穩(wěn)定性不穩(wěn)定性。 6, 7, 5, 2, 5, 8 5, 2, 5 6 7, 8 65 private static int rando

50、mizedPartition (int p, int r) int i = random(p,r); MyMath.swap(a, i, p); return partition (p, r); 快速排序算法的性能取決于劃分的對(duì)稱性。通過(guò)修改 算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排 序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被 劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)， 這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃 分是較對(duì)稱的。 int i=randomizedpartition(p,r), j=i-p+1; if (k=j) return rando

51、mizedSelect(p,i,k); else return randomizedSelect(i+1,r,k-j); 在最壞情況下，算法randomizedSelect需要O(n2)計(jì)算時(shí)間 但可以證明，算法randomizedSelect可以在O(n)平均時(shí)間內(nèi) 找出n個(gè)輸入元素中的第k小元素。 67 如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得 按這個(gè)基準(zhǔn)所劃分出的2個(gè)子數(shù)組的長(zhǎng)度都至少 為原數(shù)組長(zhǎng)度的倍(01是某個(gè)正常數(shù))，那 么就可以在最壞情況下在最壞情況下用O(n)時(shí)間完成選擇任 務(wù)。 例如，若=9/10，算法遞歸調(diào)用所產(chǎn)生的子 數(shù)組的長(zhǎng)度至少縮短1/10。所以，在最壞情 況下，算法

52、所需的計(jì)算時(shí)間T(n)滿足遞歸式 T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。 68 l將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能 有一個(gè)組不是5個(gè)元素。用任意一種排序算法，將每組中的 元素排好序，并取出每組的中位數(shù)，共n/5個(gè)。 l遞歸調(diào)用select來(lái)找出這n/5個(gè)元素的中位數(shù)。如果 n/5是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)。以這個(gè) 元素作為劃分基準(zhǔn)。 設(shè)所有元素互不相同。在這種情況下， 找出的基準(zhǔn)x至少比3(n-5)/10個(gè)元素 大，因?yàn)樵诿恳唤M中有2個(gè)元素小于 本組的中位數(shù)，而n/5個(gè)中位數(shù)中又 有(n-5)/10個(gè)小于基準(zhǔn)x。同理，基準(zhǔn) x也至少比

53、3(n-5)/10個(gè)元素小。而當(dāng) n75時(shí)，3(n-5)/10n/4所以按此基 準(zhǔn)劃分所得的2個(gè)子數(shù)組的長(zhǎng)度都至 少縮短1/4。 69 private static Comparable select (int p, int r, int k) if (r-p5) /用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組ap:r排序; bubbleSort(p,r); return ap+k-1; /將ap+5*i至ap+5*i+4的第3小元素 /與ap+i交換位置; /找中位數(shù)的中位數(shù)，r-p-4即上面所說(shuō)的n-5 for ( int i = 0; i=(r-p-4)/5; i+ ) int s=p+5*i, t=s+4

54、; for (int j=0;j3;j+) bubble(s,t-j); MyMath.swap(a, p+i, s+2); Comparable x = select(p, p+(r-p-4)/5, (r-p+6)/10); int i=partition(p,r,x), j=i-p+1; if (k=j) return select(p,i,k); else return select(i+1,r,k-j); 復(fù)雜度分析復(fù)雜度分析 T(n)=O(n) 75 75 )4/3()5/( )( 2 1 n n nTnTnC C nT 上述算法將每一組的大小定為5，并選取75作為是否作遞歸 調(diào)用的

55、分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式中2個(gè)自變量之和 n/5+3n/4=19n/20=n，01。這是使T(n)=O(n)的關(guān)鍵之 處。當(dāng)然，除了5和75之外，還有其他選擇。 70 給定平面上n個(gè)點(diǎn)的集合S，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)組 成的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)間的距離最小。 u為了使問(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)題平衡子問(wèn)題的思想，用S中各點(diǎn)坐標(biāo)的中位數(shù)來(lái)作分割點(diǎn)。 遞歸地在S1和S2上找出其最接近點(diǎn)

56、對(duì)p1,p2和q1,q2，并 設(shè)d=min|p1-p2|,|q1-q2|，S中的最接近點(diǎn)對(duì)或者是p1,p2， 或者是q1,q2，或者是某個(gè)p3,q3，其中p3S1且q3S2。 能否在線性時(shí)間內(nèi)找到能否在線性時(shí)間內(nèi)找到p3,q3？ 71 u如果S的最接近點(diǎn)對(duì)是p3,q3，即|p3-q3|d，則p3和q3兩者 與m的距離不超過(guò)d，即p3(m-d,m，q3(m,m+d。 u由于在S1中，每個(gè)長(zhǎng)度為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)就是中的點(diǎn)，則此點(diǎn)就

57、是S1中最大點(diǎn)。中最大點(diǎn)。 u因此，我們用線性時(shí)間就能找到區(qū)間(m-d,m和(m,m+d中所 有點(diǎn)，即p3和q3。從而我們用線性時(shí)間就可以將從而我們用線性時(shí)間就可以將S1的解和的解和S2 的解合并成為的解合并成為S的解的解。 能否在線性時(shí)間內(nèi)找到能否在線性時(shí)間內(nèi)找到p3,q3？ 72 u下面來(lái)考慮二維的情形。 選取一垂直線l:x=m來(lái)作為分割直線。其中m為S中各點(diǎn)x坐 標(biāo)的中位數(shù)。由此將S分割為S1和S2。 遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè) d=mind1,d2，S中的最接近點(diǎn)對(duì)或者是d，或者是某個(gè)p,q， 其中pP1且qP2。 能否在線性時(shí)間內(nèi)找到能否在線性時(shí)間內(nèi)找到p,q

58、？ 73 u考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對(duì)的候 選者，則必有distance(p，q)d。滿足這個(gè)條件的滿足這個(gè)條件的P2中的點(diǎn)中的點(diǎn) 一定落在一個(gè)一定落在一個(gè)d2d的矩形的矩形R中中 u由d的意義可知，P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由 此可以推出矩形矩形R中最多只有中最多只有6個(gè)個(gè)S中的點(diǎn)中的點(diǎn)。 u因此，在分治法的合并步驟中最多只需要檢查最多只需要檢查6n/2=3n個(gè)個(gè) 候選者候選者 能否在線性時(shí)間內(nèi)找到能否在線性時(shí)間內(nèi)找到p3,q3？ 證明證明:將矩形R的長(zhǎng)為2d的邊3等分，將它的長(zhǎng)為 d的邊2等分，由此導(dǎo)出6個(gè)(d/2)(2d/3)的矩形。 若矩形R中

59、有多于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 36 25 )3/2()2/()()()()(dddvyuyvxux 74 為了確切地知道要檢查哪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)

60、，對(duì)排好序的點(diǎn)列 作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候 選者。對(duì)P1中每一點(diǎn)最多只要檢查P2中排好 序的相繼6個(gè)點(diǎn)。 75 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=pS|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