王晓东《算法设计与分析》课件

1中国计算机学会“21世纪大学本科计算机专业系列教材”算法设计与分析王晓东编著2主要内容介绍•第1章算法引论•第2章递归与分治策略•第3章动态规划•第4章贪心算法•第5章回溯法•第6章分支限界法3主要内容介绍（续）•第7章概率算法•第8章NP完全性理论•第9章近似算法•第10章算法优化策略4第1章算法引论•1.1算法与程序•1.2表达算法的抽象机制•1.3描述算法•1.4算法复杂性分析本章主要知识点：51.1算法与程序•输入：有零个或多个外部量作为算法的输入。•输出：算法产生至少一个量作为输出。•确定性：组成算法的每条指令清晰、无歧义。•有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。是满足下述性质的指令序列。算法：程序：61.从机器语言到高级语言的抽象1.2表达算法的抽象机制高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；72.抽象数据类型1.2表达算法的抽象机制抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。8在本书中，采用Java语言描述算法。1.Java程序结构1.3描述算法以下，对Java语言的若干重要特性作简要概述。（1）Java程序的两种类型：应用程序和applet区别：应用程序的主方法为main，其可在命令行中用命令语句java应用程序名来执行；applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行。（2）包：java程序和类可以包(packages)的形式组织管理。（3）import语句：在java程序中可用import语句加载所需的包。例如，importjava.io.*;语句加载java.io包。91.3描述算法2.Java数据类型数据类型基本数据类型：详见下页表1-1非基本数据类型：如Byte,Integer,Boolean,String等。Java对两种数据类型的不同处理方式：对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）。如:intk;对非基本数据类型：语句Strings;并不建立具有数据类型String的对象，而是建立一个类型String的引用对象，数据类型为String的对象可用下面的new语句建立。s=newString(“Welcome”);Strings=newString(“Welcome”);101.3描述算法表格1-1Java基本数据类型类型缺省值分配空间（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]111.3描述算法3.方法在Java中，执行特定任务的函数或过程统称为方法(methods)。例如，java的Math类给出的常见数学计算的方法如下表所示：方法功能方法功能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的正切121.3描述算法3.方法2baba计算表达式值的自定义方法ab描述如下：publicstaticintab(inta,intb){return(a+b+Math.abs(a-b))/2;}（1）方法参数：Java中所有方法的参数均为值参数。上述方法ab中，a和b是形式参数，在调用方法时通过实际参数赋值。（2）方法重载：Java允许方法重载，即允许定义有不同签名的同名方法。上述方法ab可重载为：publicstaticdoubleab(doublea,doubleb){return(a+b+Math.abs(a-b))/2.0;}131.3描述算法4.异常Java的异常提供了一种处理错误的方法。当程序发现一个错误，就引发一个异常，以便在合适地方捕获异常并进行处理。通常用try块来定义异常处理。每个异常处理由一个catch语句组成。publicstaticvoidmain(String[]args){try{f();}catch(exception1){异常处理;}catch(exception2){异常处理;}…finally{finally块;}}141.3描述算法5.Java的类(4)访问修饰公有(public)私有(private)保护(protected)Java的类一般由4个部分组成：(1)类名(2)数据成员(3)方法151.3描述算法6.通用方法下面的方法swap用于交换一维整型数组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;}该方法只适用于整型数组该方法具有通用性，适用于Object类型及其所有子类以上方法修改如下：161.3描述算法6.通用方法（1）Computable界面publicstaticComputablesum(Computable[]a,intn){if(a.length==0)returnnull;Computablesum=(Computable)a[0].zero();for(inti=0;in;i++)sum.increment(a[i]);returnsum;}利用此界面使方法sum通用化171.3描述算法6.通用方法（2）java.lang.Comparable界面Java的Comparable界面中惟一的方法头compareTo用于比较2个元素的大小。例如java.lang.Comparable.x.compareTo(y)返回x-y的符号，当xy时返回负数，当x=y时返回0，当xy时返回正数。（3）Operable界面有些通用方法同时需要Computable界面和Comparable界面的支持。为此可定义Operable界面如下:publicinterfaceOperableextendsComputable,Comparable{}（4）自定义包装类由于Java的包装类如Integer等已定义为final型，因此无法定义其子类，作进一步扩充。为了需要可自定义包装类。181.3描述算法7.垃圾收集8.递归Java的new运算用于分配所需的内存空间。例如，int[]a=newint[500000];分配2000000字节空间给整型数组a。频繁用new分配空间可能会耗尽内存。Java的垃圾收集器会适时扫描内存，回收不用的空间（垃圾）给new重新分配。Java允许方法调用其自身。这类方法称为递归方法。publicstaticintsum(int[]a,intn){if(n==0)return0;elsereturna[n-1]+sum(a,n-1);}计算一维整型数组前n个元素之和的递归方法191.4算法复杂性分析算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。（通常，让A隐含在复杂性函数名当中）201.4算法复杂性分析最坏情况下的时间复杂性：),(maxmaxINT(N)TNDI),(max1INetkiiiDIN),(*1INetkiii),(*INT最好情况下的时间复杂性：),(minminINT(N)TNDI),(min1INetkiiiDIN)~,(1INetkiii)~,(INT平均情况下的时间复杂性：NDIINTIP(N)T),()(avgNDIkiiiINetIP),()(1其中DN是规模为N的合法输入的集合；I*是DN中使T(N,I*)达到Tmax(N)的合法输入；是中使T(N,)达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。I~I~211.4算法复杂性分析算法复杂性在渐近意义下的阶：渐近意义下的记号：O、Ω、θ、o设f(N)和g(N)是定义在正数集上的正函数。O的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(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)。221.4算法复杂性分析Ω的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。即f(N)的阶不低于g(N)的阶。θ的定义：定义f(N)=θ(g(N))当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))。此时称f(N)与g(N)同阶。o的定义：对于任意给定的ε＞0，都存在正整数N0，使得当NN0时有f(N)/Cg(N)ε,则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N))。例如，4NlogN+7=o(3N2+4NlogN+7)。23第2章递归与分治策略24•将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=•对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。25算法总体思想•对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。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