第1章算法導論詳解.ppt

1、算法設計與分析 Algorithm Design and Analysis,上海理工大學 光電信息與計算機工程學院 高麗萍,Tel :Email : Office: Room 602（新圖書館樓602房間）,First Example: Identifying Genes in Human DNA (基因識別),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億組化學基對組成人類DNA，如何界定這些序列，從而進行基因識別） Computer: 3G Hz CPU, 3*109B/s, suppose that it executes one billion instructions per second （設該計算機的運行速度為 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,全國居民身份證管理系統(tǒng)： n = 1.3109 人 國家安全防護指紋識別系統(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 算法設計與分析，呂國英編著，清華大學出版社，2005年。 算法設計與分析，王曉東編著，清華大學出版社 .,“計算機算法

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

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

7、(4)即有限性。,是滿足下述性質(zhì)的指令序列。,算法：,程序：,9,1.從機器語言到高級語言的抽象,1.2表達算法的抽象機制,高級程序設計語言的主要好處是：,（4）把繁雜瑣碎的事務交給編譯程序，所以自動化程度高，開發(fā)周期短，程序員可以集中時間和精力從事更重要的創(chuàng)造性勞動，提高程序質(zhì)量。,（1）高級語言更接近算法語言，易學、易掌握，一般工程技術人員只需 要幾周時間的培訓就可以勝任程序員的工作；,（2）高級語言為程序員提供了結構化程序設計的環(huán)境和工具，使得設計出來的程序可讀性好，可維護性強，可靠性高；,（3）高級語言不依賴于機器語言，與具體的計算機硬件關系不大，因而所寫出來的程序可植性好、重用率高；

8、,10,2.抽象數(shù)據(jù)類型,1.2表達算法的抽象機制,抽象數(shù)據(jù)類型是算法的一個數(shù)據(jù)模型連同定義在該模型上 并作為算法構件的一組運算。,抽象數(shù)據(jù)類型帶給算法設計的好處有：,（1）算法頂層設計與底層實現(xiàn)分離； （2）算法設計與數(shù)據(jù)結構設計隔開，允許數(shù)據(jù)結構自由選擇； （3）數(shù)據(jù)模型和該模型上的運算統(tǒng)一在ADT中，便于空間和時間耗費的折衷； （4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維護性； （5）算法自然呈現(xiàn)模塊化； （6）為自頂向下逐步求精和模塊化提供有效途徑和工具； （7）算法結構清晰，層次分明，便于算法正確性的證明和復雜性的分析。,11,在本書中，采用Java語言描述算法。 1.Java程序結

9、構,1.3描述算法,以下，對Java語言的若干重要特性作簡要概述。,（1）Java程序的兩種類型：應用程序和applet 區(qū)別：應用程序的主方法為main，其可在命令行中用命令 語句 java 應用程序名 來執(zhí)行； applet的主方法為init，其必須嵌入HTML文件，由 Web瀏覽器或applet閱讀器來執(zhí)行。,（2）包：java程序和類可以包(packages)的形式組織管理。,（3）import語句：在java程序中可用import語句加載所需的包。 例如，import java.io.*;語句加載java.io包。,12,1.3描述算法,2.Java數(shù)據(jù)類型,Java對兩種數(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í)行特定任務的函數(shù)或過程統(tǒng)稱為方法(methods) 。 例如，java的Math類給出的常見數(shù)學計算的方法如下表所示：,15,1.3描述算法,3.方法,計算表達式 值的自定義方法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ù)賦值。,（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的異常提供了一種處理錯誤的方法。當程序發(fā)現(xiàn)一個錯誤，就引發(fā)一個異常，以便在合適地方捕獲異常并進行處理。,通常用try塊來定義異常處理。每個異常處理由一個catch語句組成。,public static void main(Str

12、ing args) try f ( ); catch (exception1) 異常處理; catch (exception2) 異常處理; finally finally塊; ,17,1.3描述算法,5.Java的類,(4)訪問修飾,Java的類一般由4個部分組成：,(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個元素的大小。例如java.lang.CpareTo(y) 返回x-y的符號，當xy時返 回正數(shù)。,（3）Operable 界面,有些通用方法同時需要Computable界面和Comparable 界面 的支持。為此可定義Operable界面如下:,public interface Operable extends Com

15、putable, Comparable ,（4）自定義包裝類,由于Java的包裝類如Integer等已定義為final型，因此無法 定義其子類，作進一步擴充。為了需要可自定義包裝類。,21,1.3描述算法,7.垃圾收集 8.遞歸,Java的new運算用于分配所需的內(nèi)存空間。 例如， int a = new int500000; 分配2000000字節(jié)空間 給整型數(shù)組a。頻繁用new分配空間可能會耗盡內(nèi)存。Java的垃 圾收集器會適時掃描內(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); ,計算一維整型數(shù)組前n個元素之和的遞歸方法,22,1.4算法復雜性分析,算法復雜性是算法運行所需要的計算機資源的量， 需要時間資源的量稱為時間復雜性，需要的空間資源的 量稱為空間復雜性。這個量應該只依賴于算法要解的問 題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用 N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法 本身，而且用C表示復雜性，那么，應該有C=F(N,I,A)。 一般把時間復雜性和空間復雜性分開，并分別用T和S來 表示，則有： T=T(N,I)和S=S(N,I) 。 （通

17、常，讓A隱含在復雜性函數(shù)名當中）,23,1.4算法復雜性分析,最壞情況下的時間復雜性：,最好情況下的時間復雜性：,平均情況下的時間復雜性：,其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N, I*) 達到Tmax(N)的合法輸入； 是中使T(N, )達到Tmin(N)的合法 輸入；而P(I)是在算法的應用中出現(xiàn)輸入I的概率。,24,1.4算法復雜性分析,算法復雜性在漸近意義下的階：,漸近意義下的記號：O、o 設f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。,O的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當NN0時有f(N)Cg(N)，則稱函數(shù)f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N)。即f(N)的階不高于g(N)的階。,根據(jù)O的定義，容易證明它有如下運算規(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是一個正的常數(shù)； (6)f=O(f)。,25,1.4算法復雜