1、算法設(shè)計(jì)與分析 Algorithm Design and Analysis,上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院 高麗萍,Tel :Email : Office: Room 602（新圖書館樓602房間）,First Example: Identifying Genes in Human DNA (基因識(shí)別),Identifying all the 100,000 genes in human DNA determining the sequences of the 3 billion(109) chemical base pairs that make up hu

2、man DNA. （30億組化學(xué)基對(duì)組成人類DNA，如何界定這些序列，從而進(jìn)行基因識(shí)別） Computer: 3G Hz CPU, 3*109B/s, suppose that it executes one billion instructions per second （設(shè)該計(jì)算機(jī)的運(yùn)行速度為 10億條基本指令/s ） Input size: n = 3*109 Insertion sort: running time n2,t = s/v :,3,First Example: Identifying Genes in Human DNA,Identifying all the 100,0

3、00 genes in human DNA determining the sequences of the 3 billion(109) chemical base pairs that make up human DNA. Insertion sort: running time n2 Merge sort: running time nlgn,全國(guó)居民身份證管理系統(tǒng)： n = 1.3109 人 國(guó)家安全防護(hù)指紋識(shí)別系統(tǒng)：n = 1.3109 人,4,Algorithm Analysis and Design,Students：undergraduate, graduate Course

4、property：base, core, . in computing Bibliography Introduction to Algorithms(Second Edition), T. H. Cormen, C. E. Leiserson, R. L. Rivest (2002, Turing Award), The MIT Press The Art of Computer Programming, Donald E, Knuth 1974, Turing Award 算法設(shè)計(jì)與分析，呂國(guó)英編著，清華大學(xué)出版社，2005年。 算法設(shè)計(jì)與分析，王曉東編著，清華大學(xué)出版社 .,“計(jì)算機(jī)算法

5、的圣經(jīng)”,“計(jì)算機(jī)程序設(shè)計(jì) 理論的荷馬史詩(shī)”,網(wǎng)友：“沒(méi)有讀過(guò)Intro，不能算是一個(gè)真正的程序員”,Bill Gates: “如果你認(rèn)為你是一名真正優(yōu)秀的程序員，請(qǐng)讀Knuth的計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)，如果你能讀懂整套書的話，請(qǐng)給我發(fā)一份你的簡(jiǎn)歷。”,5,Algorithm Design and Analysis,學(xué)習(xí)方式 聽(tīng)課上機(jī)實(shí)踐（作業(yè)）考試 15% 15% 70% 課堂要求 學(xué)術(shù)很自由，課堂很嚴(yán)肅：不遲到、早退；不允許接聽(tīng)電話、大聲聊天 考核形式 出勤率：about 15% 大作業(yè)（算法實(shí)現(xiàn)2-3個(gè)）：about 15% 期末閉卷考試： about 70% 課程安排 課堂講解：基本理論講

6、解，基本方法的介紹分析 上機(jī)實(shí)踐：基本習(xí)題和經(jīng)典習(xí)題的上機(jī)實(shí)踐,6,主要內(nèi)容介紹,第1章算法引論 第2章 算法基本設(shè)計(jì)技巧 第3章分治策略 第4章動(dòng)態(tài)規(guī)劃 第5章貪心算法 第6章回溯法 第7章分支限界法,7,第1章 算法引論,1.1算法與程序 1.2表達(dá)算法的抽象機(jī)制 1.3描述算法 1.4算法復(fù)雜性分析,本章主要知識(shí)點(diǎn)：,8,1.1算法與程序,輸 入：有零個(gè)或多個(gè)外部量作為算法的輸入。 輸 出：算法產(chǎn)生至少一個(gè)量作為輸出。 確定性：組成算法的每條指令清晰、無(wú)歧義。 有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。,是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。 程序可以不滿足算法的性質(zhì)

7、(4)即有限性。,是滿足下述性質(zhì)的指令序列。,算法：,程序：,9,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)的程序可植性好、重用率高；

8、,10,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ù)雜性的分析。,11,在本書中，采用Java語(yǔ)言描述算法。 1.Java程序結(jié)

9、構(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ǔ)句加載所需的包。 例如，import java.io.*;語(yǔ)句加載java.io包。,12,1.3描述算法,2.Java數(shù)據(jù)類型,Java對(duì)兩種數(shù)據(jù)類型的

10、不同處理方式：,s = new String(“Welcome”); String s = new String(“Welcome”);,13,1.3描述算法,表格1-1 Java基本數(shù)據(jù)類型,14,1.3描述算法,3.方法,在Java中，執(zhí)行特定任務(wù)的函數(shù)或過(guò)程統(tǒng)稱為方法(methods) 。 例如，java的Math類給出的常見(jiàn)數(shù)學(xué)計(jì)算的方法如下表所示：,15,1.3描述算法,3.方法,計(jì)算表達(dá)式 值的自定義方法ab描述如下：,public static int ab(int a, int b) return (a+b+Math.abs(a-b)/2; ,（1）方法參數(shù)：Java中所有方法

11、的參數(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; ,16,1.3描述算法,4.異常,Java的異常提供了一種處理錯(cuò)誤的方法。當(dāng)程序發(fā)現(xiàn)一個(gè)錯(cuò)誤，就引發(fā)一個(gè)異常，以便在合適地方捕獲異常并進(jìn)行處理。,通常用try塊來(lái)定義異常處理。每個(gè)異常處理由一個(gè)catch語(yǔ)句組成。,public static void main(Str

12、ing args) try f ( ); catch (exception1) 異常處理; catch (exception2) 異常處理; finally finally塊; ,17,1.3描述算法,5.Java的類,(4)訪問(wèn)修飾,Java的類一般由4個(gè)部分組成：,(1)類名,(2)數(shù)據(jù)成員,(3)方法,18,1.3描述算法,6.通用方法,下面的方法swap用于交換一維整型數(shù)組a的位置i和位置j處的值。,public static void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp; ,public static

13、 void swap(object a, int i, int j) object temp = ai; ai = aj; aj = temp; ,該方法只適用于 整型數(shù)組,該方法具有通用性，適用于Object類型及其所有子類,以上方法修改如下：,19,1.3描述算法,6.通用方法,（1）Computable界面,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;

14、 i+) sum.increment(ai); return sum; ,利用此界面使 方法sum通用化,20,1.3描述算法,6.通用方法,（2）java.lang.Comparable 界面,Java的Comparable 界面中惟一的方法頭compareTo用于比較 2個(gè)元素的大小。例如java.lang.CpareTo(y) 返回x-y的符號(hào)，當(dāng)xy時(shí)返 回正數(shù)。,（3）Operable 界面,有些通用方法同時(shí)需要Computable界面和Comparable 界面 的支持。為此可定義Operable界面如下:,public interface Operable extends Com

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

16、nt n) if (n=0) return 0; else return an-1+sum(a,n-1); ,計(jì)算一維整型數(shù)組前n個(gè)元素之和的遞歸方法,22,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) 。 （通

17、常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中）,23,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的概率。,24,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)。,25,1.4算法復(fù)雜