第1章算法导论详解优秀PPT.ppt

《第1章算法导论详解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第1章算法导论详解优秀PPT.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法算法设计设计与分析与分析 Algorithm Design and Analysis 上海理工高校 光电信息与计算机工程学院高丽萍Email:lipinggaousst.edu Office:Room 602（新图书馆楼602房间）Page 2First Example:Identifying Genes in Human DNA (基因识别基因识别)lIdentifying all the 100,000 genes inhuman DNAudetermining the sequences of the3 billion(109)chemical base pairs that mak

2、e up human 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*109Insertion sort:running time n2t=s/v :Page 33First Example:Identifying Genes in Human DNAlIdentifying all the 100,000 ge

3、nes in human DNAudetermining the sequences of the 3 billion(109)chemical base pairs that make up human DNA.Insertion sort:running time n2Merge sort:running time nlgnl全国居民身份证管理系统：全国居民身份证管理系统：n=1.3109 人人l国家平安防护指纹识别系统：国家平安防护指纹识别系统：n=1.3109 人人Page 44Algorithm Analysis and DesignlStudents：undergraduate,g

4、raduatelCourse property：base,core,.in computinglBibliographylIntroduction to Algorithms(Second Edition),l T.H.Cormen,C.E.Leiserson,R.L.Rivest(2002,Turing Award),l The MIT PresslThe Art of Computer Programming,Donald E,Knuthl 1974,Turing Awardl算法设计与分析，吕国英编著，清华高校出版社，2005年。l算法设计与分析，王晓东编著，清华高校出版社l.“计算机算

5、法的圣经”“计算机程序设计理论的荷马史诗”网友：“没有读过Intro，不能算是一个真正的程序员”Bill Gates:“假如你认为你是一名真正优秀的程序员，请读Knuth的计算机程序设计艺术，假如你能读懂整套书的话，请给我发一份你的简历。”Page 55Algorithm Design and Analysis l学习方式l听课上机实践（作业）考试l15%15%70%l课堂要求l学术很自由，课堂很肃穆：不迟到、早退；不允许接听电话、大声闲聊l考核形式l出勤率：about 15%l大作业（算法实现2-3个）：about 15%l期末闭卷考试：about 70%l课程支配l课堂讲解：基本理论讲解，

6、基本方法的介绍分析l上机实践：基本习题和经典习题的上机实践Page 66主要内容介绍主要内容介绍第1章 算法引论第2章 算法基本设计技巧第3章 分治策略第4章 动态规划第5章 贪心算法第6章 回溯法第7章 分支限界法Page 77第第1 1章章 算法引论算法引论1.1算法与程序1.2表达算法的抽象机制1.3描述算法1.4算法困难性分析本章主要学问点：Page 881.1算法与程序算法与程序输 入：有零个或多个外部量作为算法的输入。输 出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。是算法用某种程序设计语言的

7、具体实现。程序可以不满足算法的性质(4)即有限性。是满足下述性质的指令序列。算法：程序：Page 991.从机器语言到高级语言的抽象1.2表达算法的抽象机制表达算法的抽象机制高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创建性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易驾驭，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员供应了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，牢靠性高；（3）高级语言不依靠于机器语言，与具体的计算机硬件关系不

8、大，因而所写出来的程序可植性好、重用率高；Page 10102.抽象数据类型1.2表达算法的抽象机制表达算法的抽象机制 抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：（1）算法顶层设计与底层实现分别；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化供应有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和困难性的分析。Page 11

9、11在本书中，接受Java语言描述算法。1.Java程序结构 1.3描述算法描述算法以下，对JavaJava语言的若干重要特性作简要概述。（1）Java程序的两种类型：应用程序和applet区分：应用程序的主方法为main，其可在吩咐行中用吩咐语句 java 应用程序名 来执行；applet的主方法为init，其必需嵌入HTML文件，由Web阅读器或applet阅读器来执行。（2）包：java程序和类可以包(packages)的形式组织管理。（3）import语句：在java程序中可用import语句加载所需的包。例如，import java.io.*;语句加载java.io包。Page 12

10、121.3描述算法描述算法2.2.JavaJava数据类型数据类型数据类型 基本数据类型：详见下页表1-1 非基本数据类型：如 Byte,Integer,Boolean,String等。Java对两种数据类型的不同处理方式：对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）。如:int k;对非基本数据类型：语句 String s;并不建立具有数据类型String的对象，而是建立一个类型String的引用对象，数据类型为String的对象可用下面的new语句建立。s=new StringString(“Welcome”);StringString s=ne

11、w StringString(“Welcome”);Page 13131.3描述算法描述算法表格表格1-1 1-1 JavaJava基本数据类型基本数据类型类型缺省值分配空间（bits）取值范围booleanfalse1true,falsebyte08-128,127charu000016u0000,uFFFFdouble0.0644.9*10-324 1.8*10308float0.0321.4*10-45 3.4*1038int032-2147483648,2147483647long0649.2*1017short016-32768,32767Page 14141.3描述算法描述算法3.

12、3.方法方法在Java中，执行特定任务的函数或过程统称为方法(methods)。例如，java的MathMath类类给出的常见数学计算的方法如下表所示：方法方法功能功能方法方法功能功能abs(x)x的绝对值max(x,y)x和y中较大者ceil(x)不小于x的最小整数min(x,y)x和y中较小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整数sqrt(x)x的平方根log(x)x的自然对数tan(x)x的正切Page 15151.3描述算法描述算法3.3.方法方法 计算表达式 值的自定义方法ab描述如下：public static

13、 int ab(int a,int b)return(a+b+Math.abs(a-b)/2;（1）方法参数：Java中全部方法的参数均为值参数。上述方法ab中，a和b是形式参数，在调用方法时通过实际参数赋值。（2）方法重载：Java允许方法重载，即允许定义有不同签名的同名方法。上述方法ab可重载为：public static double ab(double a,double b)return(a+b+Math.abs(a-b)/2.0;Page 16161.3描述算法描述算法4.4.异样异样 Java的异样供应了一种处理错误的方法。当程序发觉一个错误，就引发一个异样，以便在合适地方捕获异样

14、并进行处理。通常用try块来定义异样处理。每个异样处理由一个catch语句组成。public static void main(String args)try f();catch(exception1)异样处理;catch(exception2)异样处理;finally finally块;Page 17171.3描述算法描述算法5.5.JavaJava的类的类(4)访问修饰访问修饰公有(public)私有(private)保护(protected)Java的类一般由4个部分组成：(1)类名类名(2)数据成员数据成员(3)方法方法Page 18181.3描述算法描述算法6.6.通用方法通用方法

15、下面的方法swapswap用于交换一维整型数组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;该方法只适用于该方法只适用于整型数组整型数组该方法具有通用性，适用该方法具有通用性，适用于于ObjectObject类型及其全部子类型及其全部子类类 以上方法修改如下：以上方法修改如下：Page 19191.3描述算法描述算法6.6.通用方法通

16、用方法（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通用化通用化 Page 20201.3描述算法描述算法6.6.通用方法通用方法（2 2）java.lang.Comparable java.lang.Comparable

17、界面界面 Java的Comparable 界面中惟一的方法头compareTo用于比较2个元素的大小。例如java.lang.Comparable.x pareTo(y)返回x-y的符号，当xy时返回正数。（3 3）OperableOperable 界面界面 有些通用方法同时须要Computable界面和Comparable 界面的支持。为此可定义Operable界面如下:public interface Operable extends Computable,Comparable（4 4）自定义包装类）自定义包装类 由于Java的包装类如Integer等已定义为final型，因此无法定义其子

18、类，作进一步扩充。为了须要可自定义包装类。Page 21211.3描述算法描述算法7.7.垃圾收集垃圾收集8.8.递归递归Java的new运算用于安排所需的内存空间。例如，int a=new int500000;安排2000000字节空间给整型数组a。频繁用new安排空间可能会耗尽内存。Java的垃圾收集器会适时扫描内存，回收不用的空间（垃圾）给new重新安排。Java允许方法调用其自身。这类方法称为递归方法。public static int sum(int a,int n)if(n=0)return 0;else return an-1+sum(a,n-1);计算一维整型数组前计算一维整型

19、数组前n n个个元素之和的递归方法元素之和的递归方法 Page 22221.4算法困难性分析算法困难性分析 算法困难性是算法运行所须要的计算机资源的量，须要时间资源的量称为时间困难性，须要的空间资源的量称为空间困难性。这个量应当只依靠于算法要解的问题的规模、算法的输入和算法本身的函数。假如分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示困难性，那么，应当有C=F(N,I,A)。一般把时间困难性和空间困难性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。（通常，让A隐含在困难性函数名当中）Page 23231.4算法困难性分析算法困难性分析最坏状况

20、下的时间困难性：最好状况下的时间困难性：平均状况下的时间困难性：其中DN是规模为N的合法输入的集合；I*是DN中使T(N,I*)达到Tmax(N)的合法输入；是中使T(N,)达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。Page 24241.4算法困难性分析算法困难性分析算法困难性在渐近意义下的阶：渐近意义下的记号：O、o 设f(N)和g(N)是定义在正数集上的正函数。O O的定义：假如存在正的常数的定义：假如存在正的常数C C和自然数和自然数N0N0，使得当，使得当N N N0N0时有时有f(N)f(N)Cg(N)Cg(N)，则称函数，则称函数f(N)f(N)当当

21、N N充分大时上有界，且充分大时上有界，且g(N)g(N)是它的一是它的一个上界，记为个上界，记为f(N)=O(g(N)f(N)=O(g(N)。即。即f(N)f(N)的阶不高于的阶不高于g(N)g(N)的阶。的阶。依据O的定义，简洁证明它有如下运算规则：(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是一个正的常数；(6)f=O(f)。Page 25251.4算法困难性分析算法困难性分析 的定义：假如存在正的常数

22、的定义：假如存在正的常数C C和自然数和自然数N0N0，使得当，使得当N N N0N0时时有有f(N)f(N)Cg(N)Cg(N)，则称函数，则称函数f(N)f(N)当当N N充分大时下有界，且充分大时下有界，且g(N)g(N)是它是它的一个下界，记为的一个下界，记为f(N)=(g(N)f(N)=(g(N)。即。即f(N)f(N)的阶不低于的阶不低于g(N)g(N)的阶。的阶。的定义的定义：定义f(N)=(g(N)当且仅当f(N)=O(g(N)且f(N)=(g(N)。此时称f(N)与g(N)同阶。o o的定义：对于随意给定的的定义：对于随意给定的0 0，都存在正整数，都存在正整数N0N0，使得，使得当当N N N0N0时有时有f(N)/Cg(N)f(N)/Cg(N),则称函数则称函数f(N)f(N)当当N N充分大时的阶比充分大时的阶比g(N)g(N)低，记为低，记为f(N)=o(g(N)f(N)=o(g(N)。例如，例如，4NlogN+7=o(3N2+4NlogN+7)4NlogN+7=o(3N2+4NlogN+7)。