算法設(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ì)與分析王曉東王曉東編著編著1主要內(nèi)容介紹主要內(nèi)容介紹 第1章算法引論 第2章遞歸與分治策略 第3章動(dòng)態(tài)規(guī)劃 第4章貪心算法 第5章回溯法 第6章分支限界法2主要內(nèi)容介紹（續(xù)）主要內(nèi)容介紹（續(xù)） 第7章概率算法 第8章NP完全性理論 第9章近似算法 第10章 算法優(yōu)化策略3第第1 1章章 算法引論算法引論 1.1 算法與程序 1.2 表達(dá)算法的抽象機(jī)制 1.3 描述算法 1.4 算法復(fù)雜性分析本章主要知識(shí)點(diǎn)：41.1 算法與程序算法與程序 輸 入：有零個(gè)或多個(gè)外部量作為算法

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

3、序員的工作；（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)的程序可植性好、重用率高；62.抽象數(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ì)隔開，允許數(shù)據(jù)結(jié)構(gòu)自由選擇；（3）數(shù)據(jù)模型和該模型上的運(yùn)算統(tǒng)一在ADT中，便于空間和時(shí)間耗費(fèi)的折衷；（4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維

4、護(hù)性；（5）算法自然呈現(xiàn)模塊化；（6）為自頂向下逐步求精和模塊化提供有效途徑和工具；（7）算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜性的分析。 7在本書中，采用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，其必須嵌入HTML文件，由Web瀏覽器或applet閱讀器來(lái)執(zhí)行。（2）包：java程序和類可以包(p

5、ackages)的形式組織管理。 （3）import語(yǔ)句：在java程序中可用import語(yǔ)句加載所需的包。例如，import java.io.*;語(yǔ)句加載java.io包。 81.3 描述算法描述算法2.2.JavaJava數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)類型 基本數(shù)據(jù)類型：詳見下頁(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í)例）。如:int k;對(duì)非基本數(shù)據(jù)類型：語(yǔ)句 String s; 并不建立具有數(shù)據(jù)類型String的對(duì)象，

6、而是建立一個(gè)類型String的引用對(duì)象，數(shù)據(jù)類型為String的對(duì)象可用下面的new語(yǔ)句建立。 s = new StringString(“Welcome”);StringString s = new StringString(“Welcome”);91.3 描述算法描述算法表格表格1-1 1-1 JavaJava基本數(shù)據(jù)類型基本數(shù)據(jù)類型101.3 描述算法描述算法3.3.方法方法在Java中，執(zhí)行特定任務(wù)的函數(shù)或過(guò)程統(tǒng)稱為方法(methods) 。例如，java的MathMath類類給出的常見數(shù)學(xué)計(jì)算的方法如下表所示：111.3 描述算法描述算法3.3.方法方法 2baba計(jì)算表達(dá)式 值的自

7、定義方法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允許方法重載，即允許定義有不同簽名的同名方法。上述方法ab可重載為： public static double ab(double a, double b) return (a+b+Math.abs(a-b)/2.0; 121.3 描述算法描述算法4.4.異常異常 Java的異常提供了一種處理錯(cuò)誤的方法。

8、當(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) 異常處理; catch (exception2) 異常處理; finally finally塊; 131.3 描述算法描述算法5.5.JavaJava的類的類(4)訪問修飾訪問修飾公有(public) 私有(private)保護(hù)(protected) Java的類一般由4個(gè)部分組成：(1)類名類名(2)數(shù)據(jù)

9、成員數(shù)據(jù)成員(3)方法方法141.3 描述算法描述算法6.6.通用方法通用方法 下面的方法swapswap用于交換一維整型數(shù)組a的位置i和位置j處的值。 public static void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp; public static void swap(object a, int i, int j) object temp = ai; ai = aj; aj = temp; 該方法只適用于該方法只適用于整型數(shù)組整型數(shù)組該方法具有通用性，適用該方法具有通用性，適用于于ObjectObjec

10、t類型及其所有子類型及其所有子類類 以上方法修改如下：以上方法修改如下：151.3描述算法描述算法6.6.通用方法通用方法 （1 1）ComputableComputable界面界面 public static Computable sum(Computable 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通用化通用化 16

11、1.3 描述算法描述算法6.6.通用方法通用方法 （2 2）java.lang.Comparable java.lang.Comparable 界面界面 Java的Comparable 界面中惟一的方法頭compareTo用于比較2個(gè)元素的大小。例如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, Compar

12、able （4 4）自定義包裝類）自定義包裝類 由于Java的包裝類如Integer等已定義為final型，因此無(wú)法定義其子類，作進(jìn)一步擴(kuò)充。為了需要可自定義包裝類。 171.3 描述算法描述算法7.7.垃圾收集垃圾收集8.8.遞歸遞歸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(i

13、nt a, int n) if (n=0) return 0; else return an-1+sum(a,n-1); 計(jì)算一維整型數(shù)組前計(jì)算一維整型數(shù)組前n n個(gè)個(gè)元素之和的遞歸方法元素之和的遞歸方法 181.4 算法復(fù)雜性分析算法復(fù)雜性分析 算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(fù)雜性時(shí)間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開，

14、并分別用T和S來(lái)表示，則有： T=T(N,I)和S=S(N,I) 。（通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中） 191.4 算法復(fù)雜性分析算法復(fù)雜性分析最壞情況下的時(shí)間復(fù)雜性：),(maxmaxINT(N)TNDI),(max1INetkiiiDIN),(*1INetkiii),(*INT最好情況下的時(shí)間復(fù)雜性：),(minminINT(N)TNDI),(min1INetkiiiDIN),(1INetkiii),(INT平均情況下的時(shí)間復(fù)雜性：NDIINTIP(N)T),()(avgNDIkiiiINetIP),()(1 其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N, I*)達(dá)到Tmax

15、(N)的合法輸入； 是中使T(N, )達(dá)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。II201.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(N)=O(f(N)，則O(f)+O(g)=O(f)； (5)O(Cf(N)=O(f(N)，其中C是一個(gè)正的常數(shù)； (6)f=O(f)。 211.4 算法復(fù)雜性分析算法復(fù)雜性分析 的定義的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有f(N)Cg(