算法設(shè)計(jì)與分析詳解

1算法設(shè)計(jì)與分析ppt課件目前一頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)主要內(nèi)容介紹第1章 算法引論第2章 遞歸與分治策略第3章 動(dòng)態(tài)規(guī)劃第4章 貪心算法第5章 回溯法第6章 分支限界法目前二頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)主要內(nèi)容介紹（續(xù)）第7章 概率算法第8章 NP完全性理論第9章 近似算法第10章 算法優(yōu)化策略目前三頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)第1章算法引論1.1 算法與程序1.2 表達(dá)算法的抽象機(jī)制1.3 描述算法1.4 算法復(fù)雜性分析本章主要知識(shí)點(diǎn)：目前四頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.1 算法與程序輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令清晰、無(wú)歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(4)即有限性。

是滿足下述性質(zhì)的指令序列。算法：程序：目前五頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.從機(jī)器語(yǔ)言到高級(jí)語(yǔ)言的抽象1.2 表達(dá)算法的抽象機(jī)制高級(jí)程序設(shè)計(jì)語(yǔ)言的主要好處是：（4）把繁雜瑣碎的事務(wù)交給編譯程序，所以自動(dòng)化程度高，開(kāi)發(fā)周期短，程序員可以集中時(shí)間和精力從事更重要的創(chuàng)造性勞動(dòng)，提高程序質(zhì)量。（1）高級(jí)語(yǔ)言更接近算法語(yǔ)言，易學(xué)、易掌握，一般工程技術(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)的程序可植性好、重用率高；目前六頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.抽象數(shù)據(jù)類型1.2 表達(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中，便于空間和時(shí)間耗費(fèi)的折衷；（4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維護(hù)性；（5）算法自然呈現(xiàn)模塊化；（6）為自頂向下逐步求精和模塊化提供有效途徑和工具；（7）算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜性的分析。

目前七頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)在本書中，采用Java語(yǔ)言描述算法。1.Java程序結(jié)構(gòu)

1.3 描述算法以下，對(duì)Java語(yǔ)言的若干重要特性作簡(jiǎn)要概述。

（1）Java程序的兩種類型：應(yīng)用程序和applet 區(qū)別：應(yīng)用程序的主方法為main，其可在命令行中用命令 語(yǔ)句java應(yīng)用程序名來(lái)執(zhí)行；

applet的主方法為init，其必須嵌入HTML文件，由

Web瀏覽器或applet閱讀器來(lái)執(zhí)行。（2）包：java程序和類可以包(packages)的形式組織管理。

（3）import語(yǔ)句：在java程序中可用import語(yǔ)句加載所需的包。 例如，importjava.io.*;語(yǔ)句加載java.io包。

目前八頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法2.Java數(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í)例）。如:intk;對(duì)非基本數(shù)據(jù)類型：語(yǔ)句Strings;并不建立具有數(shù)據(jù)類型 String的對(duì)象，而是建立一個(gè)類型String的引用對(duì)象， 數(shù)據(jù)類型為String的對(duì)象可用下面的new語(yǔ)句建立。s=newString(“Welcome”);Strings=newString(“Welcome”);目前九頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法表格1-1Java基本數(shù)據(jù)類型類型缺省值分配空間（bits）取值范圍booleanfalse1[true,false]byte08[-128,127]char\u000016[\u0000,\uFFFF]double0.064±4.9*10-324~±1.8*10308float0.032±1.4*10-45~±3.4*1038int032[-2147483648,2147483647]long064±9.2*1017short016[-32768,32767]目前十頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法3.方法在Java中，執(zhí)行特定任務(wù)的函數(shù)或過(guò)程統(tǒng)稱為方法(methods)。例如，java的Math類給出的常見(jiàn)數(shù)學(xué)計(jì)算的方法如下表所示：方法功能方法功能abs(x)x的絕對(duì)值max(x,y)x和y中較大者ceil(x)不小于x的最小整數(shù)min(x,y)x和y中較小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整數(shù)sqrt(x)x的平方根log(x)x的自然對(duì)數(shù)tan(x)x的正切目前十一頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法3.方法

計(jì)算表達(dá)式 值的自定義方法ab描述如下：

publicstaticintab(inta,intb){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允許方法重載，即允許定義有不同簽名的同名方法。 上述方法ab可重載為：

publicstaticdoubleab(doublea,doubleb){return(a+b+Math.abs(a-b))/2.0;}

目前十二頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法4.異常Java的異常提供了一種處理錯(cuò)誤的方法。當(dāng)程序發(fā)現(xiàn)一個(gè)錯(cuò)誤，就引發(fā)一個(gè)異常，以便在合適地方捕獲異常并進(jìn)行處理。通常用try塊來(lái)定義異常處理。每個(gè)異常處理由一個(gè)catch語(yǔ)句組成。

publicstaticvoidmain(String[]args){try{f();}

catch(exception1){異常處理;}

catch(exception2){異常處理;}…

finally{finally塊;}}

目前十三頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法5.Java的類(4)訪問(wèn)修飾公有(public)私有(private)保護(hù)(protected)Java的類一般由4個(gè)部分組成：(1)類名(2)數(shù)據(jù)成員(3)方法目前十四頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法6.通用方法

下面的方法swap用于交換一維整型數(shù)組a的位置i和位置j處的值。

publicstaticvoidswap(int[]a,inti,intj){inttemp=a[i];a[i]=a[j];a[j]=temp;}

publicstaticvoidswap(object[]a,inti,intj){objecttemp=a[i];a[i]=a[j];a[j]=temp;}

該方法只適用于整型數(shù)組該方法具有通用性，適用于Object類型及其所有子類以上方法修改如下：目前十五頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法6.通用方法

（1）Computable界面

publicstaticComputablesum(Computable[]a,intn){if(a.length==0)returnnull;Computablesum=(Computable)a[0].zero();for(inti=0;i<n;i++)sum.increment(a[i]);returnsum;}利用此界面使方法sum通用化

目前十六頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法6.通用方法

（2）java.lang.Comparable界面Java的Comparable界面中惟一的方法頭compareTo用于比較2個(gè)元素的大小。例如java.lang.CpareTo(y)返回x-y的符號(hào)，當(dāng)x<y時(shí)返回負(fù)數(shù)，當(dāng)x=y時(shí)返回0，當(dāng)x>y時(shí)返回正數(shù)。（3）Operable

界面有些通用方法同時(shí)需要Computable界面和Comparable界面的支持。為此可定義Operable界面如下:publicinterfaceOperableextendsComputable,Comparable{}

（4）自定義包裝類由于Java的包裝類如Integer等已定義為final型，因此無(wú)法定義其子類，作進(jìn)一步擴(kuò)充。為了需要可自定義包裝類。目前十七頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.3 描述算法7.垃圾收集8.遞歸 Java的new運(yùn)算用于分配所需的內(nèi)存空間。例如，int[]a=newint[500000];分配2000000字節(jié)空間給整型數(shù)組a。頻繁用new分配空間可能會(huì)耗盡內(nèi)存。Java的垃圾收集器會(huì)適時(shí)掃描內(nèi)存，回收不用的空間（垃圾）給new重新分配。Java允許方法調(diào)用其自身。這類方法稱為遞歸方法。publicstaticintsum(int[]a,intn){if(n==0)return0;elsereturna[n-1]+sum(a,n-1);}計(jì)算一維整型數(shù)組前n個(gè)元素之和的遞歸方法

目前十八頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.4 算法復(fù)雜性分析

算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(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)中）

目前十九頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.4 算法復(fù)雜性分析最壞情況下的時(shí)間復(fù)雜性：最好情況下的時(shí)間復(fù)雜性：平均情況下的時(shí)間復(fù)雜性：其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N,I*)達(dá)到Tmax(N)的合法輸入；是中使T(N,)達(dá)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。目前二十頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.4 算法復(fù)雜性分析算法復(fù)雜性在漸近意義下的階：漸近意義下的記號(hào)：O、Ω、θ、o

設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。

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(N)=O(f(N))，則O(f)+O(g)=O(f)；(5)O(Cf(N))=O(f(N))，其中C是一個(gè)正的常數(shù)；(6)f=O(f)。

目前二十一頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)1.4 算法復(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的定義：對(duì)于任意給定的ε＞0，都存在正整數(shù)N0，使得當(dāng)NN0時(shí)有f(N)/Cg(N)ε,則稱函數(shù)f(N)當(dāng)N充分大時(shí)的階比g(N)低，記為f(N)=o(g(N))。例如，4NlogN+7=o(3N2+4NlogN+7)。

目前二十二頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)第2章遞歸與分治策略目前二十三頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。算法總體思想nT(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ī)模足夠小，很容易求出其解為止。目前二十四頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)算法總體思想對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wè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ī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。目前二十五頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)算法總體思想將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。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)目前二十六頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)算法總體思想將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。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è)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。

凡治眾如治寡，分?jǐn)?shù)是也。

----孫子兵法目前二十七頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(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í)例。目前二十八頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例1階乘函數(shù)階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。目前二十九頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例2Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，…，被稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：publicstaticintfibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}目前三十頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)目前三十一頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例3Ackerman函數(shù)當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：目前三十二頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例3Ackerman函數(shù)前2例中的函數(shù)都可以找到相應(yīng)的非遞歸方式定義：但本例中的Ackerman函數(shù)卻無(wú)法找到非遞歸的定義。目前三十三頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例3Ackerman函數(shù)A(n，m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)：M=0時(shí)，A(n,0)=n+2M=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2^n。M=3時(shí)，類似的可以推出M=4時(shí)，A(n,4)的增長(zhǎng)速度非?？欤灾劣跊](méi)有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一函數(shù)。目前三十四頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例3Ackerman函數(shù)定義單變量的Ackerman函數(shù)A(n)為，A(n)=A(n，n)。定義其擬逆函數(shù)α(n)為：α(n)=min{k｜A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。α(n)在復(fù)雜度分析中常遇到。對(duì)于通常所見(jiàn)到的正整數(shù)n，有α(n)≤4。但在理論上α(n)沒(méi)有上界，隨著n的增加，它以難以想象的慢速度趨向正無(wú)窮大。目前三十五頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例4排列問(wèn)題設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素{r1,r2,…,rn}的全排列。設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個(gè)元素，Ri=R-{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下：

當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素；當(dāng)n>1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)構(gòu)成。

目前三十六頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例5整數(shù)劃分問(wèn)題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(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。目前三十七頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)(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),n>m>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤n-1的劃分組成。(3)q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。2.1遞歸的概念例5整數(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)系。目前三十八頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例5整數(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(n,n)。

目前三十九頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)目前四十頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)2.1遞歸的概念例6Hanoi塔問(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中任一塔座上。目前四十一頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)在問(wèn)題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)題。當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單。此時(shí)，只要將編號(hào)為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n＞1時(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遞歸的概念例6Hanoi塔問(wèn)題

publicstaticvoidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}思考題：如果塔的個(gè)數(shù)變?yōu)閍,b,c,d四個(gè)，現(xiàn)要將n個(gè)圓盤從a全部移動(dòng)到d，移動(dòng)規(guī)則不變，求移動(dòng)步數(shù)最小的方案。目前四十二頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。目前四十三頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)遞歸小結(jié)解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1.采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。2.用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3.通過(guò)Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。目前四十四頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)分治法的適用條件分治法所能解決的問(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)題。因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問(wèn)題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。目前四十五頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)分治法的基本步驟divide-and-conquer(P){

if(|P|<=n0)adhoc(P);//解決小規(guī)模的問(wèn)題

dividePintosmallersubinstancesP1,P2,...,Pk；//分解問(wèn)題

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//遞歸的解各子問(wèn)題

returnmerge(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)題規(guī)模不等的做法要好。目前四十六頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)分治法的復(fù)雜性分析一個(gè)分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為n／m的子問(wèn)題去解。設(shè)分解閥值n0=1，且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í)間，則有：通過(guò)迭代法求得方程的解：注意：遞歸方程及其解只給出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)mi≤n<mi+1時(shí)，T(mi)≤T(n)<T(mi+1)。目前四十七頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)二分搜索技術(shù)分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問(wèn)題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素a[mid]，若x=a[mid]，則x在L中的位置就是mid；如果x<a[mid]，由于a是遞增排序的，因此假如x在a中的話，x必然排在a[mid]的前面，所以我們只要在a[mid]的前面查找x即可；如果x>a[i]，同理我們只要在a[mid]的后面查找x即可。無(wú)論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)?？s小了。這就說(shuō)明了此問(wèn)題滿足分治法的第二個(gè)和第三個(gè)適用條件。

分析：很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在a[i]的前面或后面查找x是獨(dú)立的子問(wèn)題，因此滿足分治法的第四個(gè)適用條件。給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。分析：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。目前四十八頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。據(jù)此容易設(shè)計(jì)出二分搜索算法：publicstaticintbinarySearch(int[]a,intx,intn){//在a[0]<=a[1]<=...<=a[n-1]中搜索x//找到x時(shí)返回其在數(shù)組中的位置，否則返回-1intleft=0;intright=n-1;

while(left<=right){intmiddle=(left+right)/2;

if(x==a[middle])returnmiddle;

if(x>a[middle])left=middle+1;

elseright=middle-1;}

return-1;//未找到x}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn)次。循環(huán)體內(nèi)運(yùn)算需要O(1)時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn)。思考題：給定a，用二分法設(shè)計(jì)出求an的算法。目前四十九頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)大整數(shù)的乘法請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)效率太低分治法:abcd復(fù)雜度分析T(n)=O(n2)沒(méi)有改進(jìn)X=Y=X=a2n/2+bY=c2n/2+d

XY=ac2n+(ad+bc)2n/2+bd

目前五十頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)大整數(shù)的乘法請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)效率太低分治法:XY=ac2n+(ad+bc)2n/2+bd

為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bdXY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd復(fù)雜度分析T(n)=O(nlog3)=O(n1.59)較大的改進(jìn)細(xì)節(jié)問(wèn)題：兩個(gè)XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問(wèn)題的規(guī)模變大，故不選擇第2種方案。目前五十一頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)大整數(shù)的乘法請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)效率太低分治法:O(n1.59)較大的改進(jìn)更快的方法??如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來(lái)，將有可能得到更優(yōu)的算法。最終的，這個(gè)思想導(dǎo)致了快速傅利葉變換(FastFourierTransform)的產(chǎn)生。該方法也可以看作是一個(gè)復(fù)雜的分治算法，對(duì)于大整數(shù)乘法，它能在O(nlogn)時(shí)間內(nèi)解決。是否能找到線性時(shí)間的算法？？？目前為止還沒(méi)有結(jié)果。目前五十二頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來(lái)計(jì)算A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的個(gè)元素所需的計(jì)算時(shí)間為O(n3)傳統(tǒng)方法：O(n3)目前五十三頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)Strassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣。由此可將方程C=AB重寫為：傳統(tǒng)方法：O(n3)分治法:由此可得：復(fù)雜度分析T(n)=O(n3)沒(méi)有改進(jìn)目前五十四頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。復(fù)雜度分析T(n)=O(nlog7)=O(n2.81)較大的改進(jìn)目前五十五頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:O(n2.81)更快的方法??Hopcroft和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)２×２矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算2×2矩陣的7次乘法這樣的方法了。或許應(yīng)當(dāng)研究３×３或５×５矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。目前最好的計(jì)算時(shí)間上界是O(n2.376)是否能找到O(n2)的算法？？？目前為止還沒(méi)有結(jié)果。目前五十六頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)棋盤覆蓋在一個(gè)2k×2k

個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。目前五十七頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)棋盤覆蓋當(dāng)k>0時(shí)，將2k×2k棋盤分割為4個(gè)2k-1×2k-1

子棋盤(a)所示。特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無(wú)特殊方格。為了將這3個(gè)無(wú)特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，如(b)所示，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為棋盤1×1。

目前五十八頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)棋盤覆蓋

publicvoidchessBoard(inttr,inttc,intdr,intdc,intsize){

if(size==1)return;intt=tile++,//L型骨牌號(hào)

s=size/2;//分割棋盤

//覆蓋左上角子棋盤

if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盤中

chessBoard(tr,tc,dr,dc,s);

else{//此棋盤中無(wú)特殊方格

//用t號(hào)L型骨牌覆蓋右下角

board[tr+s-1][tc+s-1]=t;//覆蓋其余方格

chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆蓋右上角子棋盤

if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盤中

chessBoard(tr,tc+s,dr,dc,s);

else{//此棋盤中無(wú)特殊方格

//用t號(hào)L型骨牌覆蓋左下角

board[tr+s-1][tc+s]=t;//覆蓋其余方格

chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆蓋左下角子棋盤

if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盤中

chessBoard(tr+s,tc,dr,dc,s);

else{//用t號(hào)L型骨牌覆蓋右上角

board[tr+s][tc+s-1]=t;//覆蓋其余方格

chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆蓋右下角子棋盤

if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盤中

chessBoard(tr+s,tc+s,dr,dc,s);

else{//用t號(hào)L型骨牌覆蓋左上角

board[tr+s][tc+s]=t;//覆蓋其余方格

chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}復(fù)雜度分析T(n)=O(4k)漸進(jìn)意義下的最優(yōu)算法目前五十九頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。

publicstaticvoidmergeSort(Comparablea[],intleft,intright){

if(left<right){//至少有2個(gè)元素

inti=(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)算法目前六十頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)合并排序算法mergeSort的遞歸過(guò)程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]目前六十一頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)合并排序最壞時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)穩(wěn)定性：穩(wěn)定思考題：給定有序表A[1:n]，修改合并排序算法，求出該有序表的逆序?qū)?shù)。目前六十二頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)快速排序在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。privatestaticvoidqSort(intp,intr){

if(p<r){intq=partition(p,r);//以a[p]為基準(zhǔn)元素將a[p:r]劃分成3段a[p:q-1],a[q]和a[q+1:r]，使得a[p:q-1]中任何元素小于等于a[q]，a[q+1:r]中任何元素大于等于a[q]。下標(biāo)q在劃分過(guò)程中確定。

qSort(p,q-1);//對(duì)左半段排序

qSort(q+1,r);//對(duì)右半段排序

}}快速排序是對(duì)氣泡排序的一種改進(jìn)方法它是由C.A.R.Hoare于1962年提出的目前六十三頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)快速排序privatestaticintpartition(intp,intr){inti=p,j=r+1;Comparablex=a[p];//將>=x的元素交換到左邊區(qū)域

//將<=x的元素交換到右邊區(qū)域

while(true){

while(a[++i].compareTo(x)<0);

while(a[--j].compareTo(x)>0);

if(i>=j)break;MyMath.swap(a,i,j);}a[p]=a[j];a[j]=x;

returnj;}初始序列{6,7,5,2,5,8}j--;{5,7,5,2,6,8}i++;{5,6,5,2,7,8}j--;{5,2,5,6,7,8}i++;完成快速排序具有不穩(wěn)定性。{6,7,5,2,5,8}{5,2,5}6{7,8}目前六十四頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)privatestaticintrandomizedPartition(intp,intr){inti=random(p,r);MyMath.swap(a,i,p);

return

partition(p,r);}快速排序快速排序算法的性能取決于劃分的對(duì)稱性。通過(guò)修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在a[p:r]中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)或O(logn)穩(wěn)定性：不穩(wěn)定目前六十五頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)線性時(shí)間選擇給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1≤k≤n，要求找出這n個(gè)元素中第k小的元素privatestaticComparablerandomizedSelect(intp,intr,intk){

if(p==r)returna[p];inti=randomizedpartition(p,r),j=i-p+1;

if(k<=j)return

randomizedSelect(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小元素。目前六十六頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)線性時(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ù)。例如，若ε=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長(zhǎng)度至少縮短1/10。所以，在最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。目前六十七頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個(gè)。遞歸調(diào)用select來(lái)找出這n/5個(gè)元素的中位數(shù)。如果n/5是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)。以這個(gè)元素作為劃分基準(zhǔn)。線性時(shí)間選擇設(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也至少比3(n-5)/10個(gè)元素小。而當(dāng)n≥75時(shí)，3(n-5)/10≥n/4所以按此基準(zhǔn)劃分所得的2個(gè)子數(shù)組的長(zhǎng)度都至少縮短1/4。目前六十八頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)privatestaticComparableselect(intp,intr,intk){

if(r-p<5){//用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組a[p:r]排序;

bubbleSort(p,r);

returna[p+k-1];}//將a[p+5*i]至a[p+5*i+4]的第3小元素

//與a[p+i]交換位置;//找中位數(shù)的中位數(shù)，r-p-4即上面所說(shuō)的n-5

for(inti=0;i<=(r-p-4)/5;i++){ints=p+5*i,t=s+4;

for(intj=0;j<3;j++)bubble(s,t-j);MyMath.swap(a,p+i,s+2);}Comparablex=select(p,p+(r-p-4)/5,(r-p+6)/10);inti=partition(p,r,x),j=i-p+1;

if(k<=j)return

select(p,i,k);

elsereturnselect(i+1,r,k-j);}復(fù)雜度分析T(n)=O(n)上述算法將每一組的大小定為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之外，還有其他選擇。目前六十九頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)最接近點(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{|p1-p2|,|q1-q2|}，S中的最接近點(diǎn)對(duì)或者是{p1,p2}，或者是{q1,q2}，或者是某個(gè){p3,q3}，其中p3∈S1且q3∈S2。能否在線性時(shí)間內(nèi)找到p3,q3？目前七十頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)最接近點(diǎn)對(duì)問(wèn)題如果S的最接近點(diǎn)對(duì)是{p3,q3}，即|p3-q3|<d，則p3和q3兩者與m的距離不超過(guò)d，即p3∈(m-d,m]，q3∈(m,m+d]。由于在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)就是S1中最大點(diǎn)。因此，我們用線性時(shí)間就能找到區(qū)間(m-d,m]和(m,m+d]中所有點(diǎn)，即p3和q3。從而我們用線性時(shí)間就可以將S1的解和S2的解合并成為S的解。能否在線性時(shí)間內(nèi)找到p3,q3？目前七十一頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)最接近點(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？目前七十二頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)最接近點(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的意義相矛盾。目前七十三頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)為了確切地知道要檢查哪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)題目前七十四頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)最接近點(diǎn)對(duì)問(wèn)題publicstaticdoublecpair2(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);

returnd;}復(fù)雜度分析T(n)=O(nlogn)目前七十五頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。1234567821436587341278564321876556781234658721437856341287654321目前七十六頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)循環(huán)賽日程表設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。1234567821436587341278564321876556781234658721437856341287654321目前七十七頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)第3章動(dòng)態(tài)規(guī)劃目前七十八頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=目前七十九頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)算法總體思想動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=目前八十頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。算法總體思想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)目前八十一頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Thosewhocannotrememberthepastaredoomedtorepeatit.-----GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)目前八十二頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。目前八十三頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)完全加括號(hào)的矩陣連乘積（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積是完全加括號(hào)的，則可表示為2個(gè)完全加括號(hào)的矩陣連乘積和的乘積并加括號(hào)，即16000,10500,36000,87500,34500完全加括號(hào)的矩陣連乘積可遞歸地定義為：設(shè)有四個(gè)矩陣，它們的維數(shù)分別是：總共有五中完全加括號(hào)的方式目前八十四頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)矩陣連乘問(wèn)題給定n個(gè)矩陣，其中與是可乘的，?？疾爝@n個(gè)矩陣的連乘積由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積目前八十五頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)矩陣連乘問(wèn)題給定n個(gè)矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1,2,…,n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。

算法復(fù)雜度分析：對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1...Ak)(Ak+1…An)可以得到關(guān)于P(n)的遞推式如下：目前八十六頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)矩陣連乘問(wèn)題窮舉法動(dòng)態(tài)規(guī)劃將矩陣連乘積簡(jiǎn)記為A[i:j]，這里i≤j考察計(jì)算A[i:j]的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開(kāi)，i≤k<j，則其相應(yīng)完全加括號(hào)方式為計(jì)算量：A[i:k]的計(jì)算量加上A[k+1:j]的計(jì)算量，再加上A[i:k]和A[k+1:j]相乘的計(jì)算量目前八十七頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)分析最優(yōu)解的結(jié)構(gòu)特征：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。目前八十八頁(yè)\總數(shù)三百五十五頁(yè)\編于十六點(diǎn)建立遞歸關(guān)系設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問(wèn)題的最優(yōu)值為m[1,n]當(dāng)i=j時(shí)，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n當(dāng)i<j時(shí)，可以遞歸地定義m[i,j]為：這里的維數(shù)為

的位置只有種可能目前八十九頁(yè)\總數(shù)三百五十五頁(yè)\編于