王晓东《算法设计与分析》PPT课件.ppt
《王晓东《算法设计与分析》PPT课件.ppt》由会员分享,可在线阅读,更多相关《王晓东《算法设计与分析》PPT课件.ppt(356页珍藏版)》请在咨信网上搜索。
1、中国计算机学会“21“21世纪大学本科计算机专业系列教材”算法设计与分析王晓东编著1.主要内容介绍第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法2.主要内容介绍(续)第7章概率算法第8章NP完全性理论第9章近似算法第10章 算法优化策略3.第1 1章 算法引论1.1 算法与程序1.2 表达算法的抽象机制1.3 描述算法1.4 算法复杂性分析本章主要知识点:4.1.1 算法与程序输 入:有零个或多个外部量作为算法的输入。输 出:算法产生至少一个量作为输出。确定性:组成算法的每条指令清晰、无歧义。有限性:算法中每条指令的执行次数有限,执行每条指令的时间也
2、有限。是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。是满足下述性质的指令序列。算法:程序:5.1.从机器语言到高级语言的抽象1.2 表达算法的抽象机制高级程序设计语言的主要好处是:(4)把繁杂琐碎的事务交给编译程序,所以自动化程度高,开发周期短,程序员可以集中时间和精力从事更重要的创造性劳动,提高程序质量。(1)高级语言更接近算法语言,易学、易掌握,一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作;(2)高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高;(3)高级语言不依赖于机器语言,与具体的计算机硬件
3、关系不大,因而所写出来的程序可植性好、重用率高;6.2.抽象数据类型1.2 表达算法的抽象机制 抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有:(1)算法顶层设计与底层实现分离;(2)算法设计与数据结构设计隔开,允许数据结构自由选择;(3)数据模型和该模型上的运算统一在ADT中,便于空间和时间耗费的折衷;(4)用抽象数据类型表述的算法具有很好的可维护性;(5)算法自然呈现模块化;(6)为自顶向下逐步求精和模块化提供有效途径和工具;(7)算法结构清晰,层次分明,便于算法正确性的证明和复杂性的分析。7.在本书中,采用Java语言描述算法
4、。1.1.JavaJava程序结构 1.3 描述算法以下,对JavaJava语言的若干重要特性作简要概述。(1)Java程序的两种类型:应用程序和appletapplet区别:应用程序的主方法为main,其可在命令行中用命令语句 java 应用程序名 来执行;applet的主方法为init,其必须嵌入HTML文件,由Web浏览器或applet阅读器来执行。(2)包:java程序和类可以包(packages)的形式组织管理。(3)import语句:在java程序中可用import语句加载所需的包。例如,import java.io.*;语句加载java.io包。8.1.3 描述算法2.2.Jav
5、aJava数据类型数据类型 基本数据类型:详见下页表1-1 非基本数据类型:如 Byte,Integer,Boolean,String等。Java对两种数据类型的不同处理方式:对基本数据类型:在声明一个具有基本数据类型的变量时,自动建立该数据类型的对象(或称实例)。如:int k;对非基本数据类型:语句 String s;并不建立具有数据类型String的对象,而是建立一个类型String的引用对象,数据类型为String的对象可用下面的new语句建立。s=new StringString(“Welcome”);StringString s=new StringString(“Welcome”
6、);9.1.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,3276710.1.3 描述算法3.3.方法在Java中,执行特定任务的函数或过程统称为方法(methods)。例如,java的MathM
7、ath类给出的常见数学计算的方法如下表所示:方法功能方法功能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的正切11.1.3 描述算法3.3.方法 计算表达式 值的自定义方法ab描述如下:public static int ab(int a,int b)return(a+b+Math.abs(a-b)/2;(1)方法参数:Java中所有方法的参数均为值参数。
8、上述方法ab中,a和b是形式参数,在调用方法时通过实际参数赋值。(2)方法重载:Java允许方法重载,即允许定义有不同签名的同名方法。上述方法ab可重载为:public static double ab(double a,double b)return(a+b+Math.abs(a-b)/2.0;12.1.3 描述算法4.4.异常 Java的异常提供了一种处理错误的方法。当程序发现一个错误,就引发一个异常,以便在合适地方捕获异常并进行处理。通常用trytry块来定义异常处理。每个异常处理由一个catchcatch语句组成。public static void main(String args)
9、try f();catch(exception1)异常处理;catch(exception2)异常处理;finally finally块;13.1.3 描述算法5.5.JavaJava的类(4)访问修饰公有(public)私有(private)保护(protected)Java的类一般由4个部分组成:(1)类名(2)数据成员(3)方法14.1.3 描述算法6.6.通用方法 下面的方法swapswap用于交换一维整型数组a的位置i和位置j处的值。public static void swap(int a,int i,int j)int temp=ai;ai=aj;aj=temp;public s
10、tatic void swap(object a,int i,int j)object temp=ai;ai=aj;aj=temp;该方法只适用于整型数组该方法具有通用性,适用于ObjectObject类型及其所有子类 以上方法修改如下:15.1.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.i
11、ncrement(ai);return sum;利用此界面使方法sumsum通用化 16.1.3 描述算法6.6.通用方法(2 2)java.lang.Comparable java.lang.Comparable 界面 Java的Comparable 界面中惟一的方法头compareTo用于比较2个元素的大小。例如java.lang.CpareTo(y)返回x-y的符号,当xy时返回正数。(3 3)OperableOperable 界面 有些通用方法同时需要Computable界面和Comparable 界面的支持。为此可定义Operable界面如下:public interface Ope
12、rable extends Computable,Comparable(4 4)自定义包装类 由于Java的包装类如Integer等已定义为final型,因此无法定义其子类,作进一步扩充。为了需要可自定义包装类。17.1.3 描述算法7.7.垃圾收集8.8.递归Java的newnew运算用于分配所需的内存空间。例如,int a=new int500000;分配2000000字节空间给整型数组a。频繁用new分配空间可能会耗尽内存。Java的垃圾收集器会适时扫描内存,回收不用的空间(垃圾)给new重新分配。Java允许方法调用其自身。这类方法称为递归方法。public static int su
13、m(int a,int n)if(n=0)return 0;else return an-1+sum(a,n-1);计算一维整型数组前n n个元素之和的递归方法 18.1.4 算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身,而且用C表示复杂性,那么,应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开,并分别用T和S来表示,则有:T=T(N,I)和S=S(N,I)。(通常,让A
14、隐含在复杂性函数名当中)19.1.4 算法复杂性分析最坏情况下的时间复杂性:最好情况下的时间复杂性:平均情况下的时间复杂性:其中DN是规模为N的合法输入的集合;I*是DN中使T(N,I*)达到Tmax(N)的合法输入;是中使T(N,)达到Tmin(N)的合法输入;而P(I)是在算法的应用中出现输入I的概率。20.1.4 算法复杂性分析算法复杂性在渐近意义下的阶:渐近意义下的记号:O、o 设f(N)和g(N)是定义在正数集上的正函数。O O的定义:如果存在正的常数C和自然数N0,使得当NN0时有f(N)Cg(N),则称函数f(N)当N充分大时上有界,且g(N)是它的一个上界,记为f(N)=O(g
15、(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)。21.1.4 算法复杂性分析 的定义:如果存在正的常数C和自然数N0,使得当NN0时有f(N)Cg(N),则称函数f(N)当N充分大时下有界,且g(N)是它的一个下界,记为f(N)=(g(N)。即f(N)的阶不低于g(N)的阶。的定义:定义f(N)=
16、(g(N)当且仅当f(N)=O(g(N)且f(N)=(g(N)。此时称f(N)与g(N)同阶。o o的定义:对于任意给定的0,都存在正整数N0,使得当NN0时有f(N)/Cg(N),则称函数f(N)当N充分大时的阶比g(N)低,记为f(N)=o(g(N)。例如,4NlogN+7=o(3N2+4NlogN+7)。22.第2 2章 递归与分治策略23.将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其
17、解为止。24.算法总体思想对这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)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。25.算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。nT(n)=n/2T(n/
18、4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)26.算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。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)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的
19、相同问题,以便各个击破,分而治之。凡治众如治寡,分数是也。-孙子兵法27.2.1 2.1 递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。下面来看几个实例。28.2.1 2.1 递归的概念例1 1 阶乘函数阶乘函数可递归地定义为:边界条件递归方程边界条件与递归方程
20、是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。29.2.1 2.1 递归的概念例2 Fibonacci2 Fibonacci数列无穷数列1,1,2,3,5,8,13,21,34,55,被称为Fibonacci数列。它可以递归地定义为:边界条件递归方程第n个Fibonacci数可递归地计算如下:public static int fibonacci(int n)if(n 1时,perm(R)由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)构成。36.2.1 2.1 递归的概念例5 5 整数划分问题将正整数n表示成一系列正整数之和:n
21、=n1+n2+nk,其中n1n2nk1,k1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。例如正整数6有如下11种不同的划分:6;5+1;4+2,4+1+1;3+3,3+2+1,3+1+1+1;2+2+2,2+2+1+1,2+1+1+1+1;1+1+1+1+1+1。37.(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此,q(1,m)=1。(1)q(n,1)=1,n1;当最大加数n1不大于1时,任何正整数n只有一种划分形式,即 (4)q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n
22、-1 的划分组成。(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。2.1 2.1 递归的概念例5 5 整数划分问题前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解。在本例中,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。38.2.1 2.1 递归的概念例5 5 整数划分问题前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解。在本例中,如果设p(n)为正整数n的划分数,则难以
23、找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。39.40.2.1 2.1 递归的概念例6 Hanoi6 Hanoi塔问题设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则:规则1:每次只能移动1个圆盘;规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;规则3:在满足移动规则1和2的前提下,可将圆盘移至a
24、,b,c中任一塔座上。41.在问题规模较大时,较难找到一般的方法,因此我们尝试用递归技术来解决这个问题。当n=1时,问题比较简单。此时,只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n1时,需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c,然后,将剩下的最大圆盘从塔座a移至塔座b,最后,再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见,n个圆盘的移动问题可分为2次n-1个圆盘的移动问题,这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。2.1 2.1 递归的概念例6 Hanoi6 Hanoi塔问题 p
25、ublic static void hanoi(int n,int a,int b,int c)if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);思考题:如果塔的个数变为思考题:如果塔的个数变为a,b,c,da,b,c,d四四个,现要将个,现要将n n个圆盘从个圆盘从a a全部移动到全部移动到d d,移动规则不变,求移动步数最小的,移动规则不变,求移动步数最小的方案。方案。42.递归小结优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。缺点:递归算法的运行效率较低,无论是耗费的计算时间还
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法设计与分析 王晓东 算法 设计 分析 PPT 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。