算法分析第一章导论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,主讲教师：孙成敏,suncmjlu.edu,2021年3月-2021年6月,计算机算法,设计与分析,2,课程设置,类别：专业必修课,学分：,3,学分,理论学时：,48,习题课学时：,8,开课周数：,1-14,周,3,根本内容,导引 第一、二章,根本的算法设计策略,分治法 第四章,贪心方法 第五章,动态规划 第六章,回溯法 第八章,分支限界法 第九章,根本算法分析方法,NP-难度和NP-完全问题 第十章,4,学习目标,掌握根本的算法设计方法,掌握进行算法分析的根本方法时间、空间复杂度分析,灵活运用根本的算法设计方法，解决实际问题,5,参考书目,计算机算法设计与分析 王晓东 电子工业,计算机算法设计与分析 苏德富 电子工业,8,问：“交给你的问题，解决方法想出来了吗？,答：“我找不到一个有效的方法来解决它，因为这样的方法是不存在的。,要证明一个问题不存在有效的方法，往往比寻找一种有效方法更难。,9,问：“交给你的问题，解决方法想出来了吗？,答：“我找到了一方法来解决它，理论上可实现的，但是以我们目前的力量实现它是不可能的。,方法消耗的资源太大了,。,问题解决的好吗？,10,现实世界的两个问题,问题能解决吗？,(,可计算性,),问题解决的好吗？,(,计算复杂性,),11,可计算性研究的范畴,计算机虽然神通广阔，还是在人的控制下工作。,计算机并非什么都能做，有的事情理论上它根本做不了。,讨论哪些事计算机能做，哪些事计算机做不了，属于可计算性理论研究的范畴。,12,一个满足可计算性的问题,26个英文字母全排列，它的排列数为,26！41026,以每年365天计算，共有,3652436003.1536107秒。,以每秒能完成107个排列的超高速电子计算机来做这项工作，需要 41026/(3.1536107107)1.21012年千亿年。,13,有一些问题虽然在理论上能够由计算机解决，但因其算法占用资源太多而无法实际完成，因此需要选择其他算法或改进算法。,要知道算法的优劣好坏，就要对算法需要多少计算时间和存储空间做定量的分析。,算法分析研究的范畴,迄今为止，已有,20%,左右的计算机科学家因其在计算复杂性方面的研究工作而获得图灵奖。,14,本课程的计算机,本课程指的计算机是和图灵机计算能力等价的、冯诺伊曼体系结构计算机，即,确定性图灵机。,量子计算机是非确定性图灵机，其算法和计算复杂性完全不同。,15,几个典型的非数值计算问题,巡回推销员问题,n,皇后问题,背包问题,16,巡回推销员问题,动态规划 设有n个城市，任意两城市间之距离，现有一推销员想从某一城市出发巡回经过每一城市且每城市只经过一次，最后又回到出发点，问如何找一条最短路径。试一试求出最短路径。,17,n,皇后问题,回溯法 这是高斯1850年提出的一个著名问题：国际象棋中的“皇后在横向、竖向和斜向都能走步和吃子，问在nn 格的棋盘上如何能摆上n个皇后而使她们都不能互相吃。,当n很大时，问题很难。,对于n8，现此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。设n4，试一试。,18,背包问题,有一旅行者要从,3,种物品中选取不超过,50,公斤重的行李随身携带，要求总价值最大。,物品,1,重,10,千克，价值,60,元；物品,2,重,20,千克，价值,100,元；物品,3,重,30,千克，价值,120,元。,动态规划,物品不可分割的前提下，求总价值最大。,贪心算法,物品可以分割的前提下，求总价值最大。,19,开展历史,D.Knuth,?The Art of Computer Programming?,A.V.Aho,J.Hopcroft,J.Ullman,?The Design and Analysis of computer Algothms?,Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,?Introduction to Algorithms?,20,第二章 导 引与根本数据结构,2.1 算法,2.2 分析算法及数学根底,2.3 用SPARKS语言写算法,2.4 根本数据结构略,21,2.1,算 法,什么是算法,算法的重要特性,计算过程与算法的区别,问题的求解过程,算法学习的根本内容,22,什么是算法,算法是解决一确定类问题的任意一种特殊的方法。,数值计算方法,非数值计算方法,算法的非形式描述：算法就是一组有穷的规那么，它规定了解决某一特定类型问题的一系列运算。,求解数值问题，插值计算、数值积分等。,求解非数值问题，主要进行判断比较。,23,算法的五个重要特性,确定性：每一种运算必须要有确切的定义，无二义性；,能行性：运算都是根本运算，原那么上能在有限,时间内完成；,输 入：有0个或多个输入；,输 出：一个或多个输出；,有穷性：在执行了有穷步运算后终止；,仅仅有穷还不够，还要在现代计算机上有效才行。,24,计算过程与算法的区别,计算过程可以不满足算法的性质,(5),有穷性。,例如操作系统，当没有任务时，操作系统并不终止，而是处于等待状态，直到有新的任务启动，因而不是一个算法。,程序,算法,数据结构,(By Wirth,),25,问题的求解过程,证明正确性,分析算法,理解问题,精确解或近似解,算法设计策略,选择数据结构,设计算法,设计程序,26,算法学习的根本内容,如何设计算法,如何表示算法,如何确认算法,如何分析算法,如何测试程序,27,如何设计算法,面对具体问题，运用一些根本设计策略，规划算法。,被实践证明是有用的,计算机科学、运筹学、电器工程等领域,设计出很多精致有效的好算法,掌握这些策略，设计出更多的好算法。,28,如何表示算法,设计的算法要用恰当的方式表示出来,采用结构程序设计的方式,SPARKS,程序设计语言,简单明了,29,如何确认算法,算法确认,(algorithm validation),证明该算法对所有可能的合法输入，都能给出正确答案,算法确认的目的,确保该算法能正确无误地工作,穷举法,推理,数学归纳法、反证法,构造性证明,测试,30,如何分析算法,分析执行一个算法时，,占用,CPU,时间完成运算；,占用存储器的存储空间，存放程序和数据。,即对一个算法需要多少计算时间和存储空间，做定量分析。,31,测试程序,调试,调试只能指出有错误，而不能指出它们不存在错误。,源于程序正确性的证明还没有取得突破性进展。,时空分布图,用各种给定数据执行调试后的程序,测定计算时间和空间,印证之前的分析是否正确,指出实现最优化的有效逻辑位置,32,第二章 导 引,2.1 算法,2.2 分析算法及数学根底,2.3 用SPARKS语言写算法,2.4 根本数据结构,33,2.2,分析算法,算法分析目的,算法分析的准备工作,计算时间的渐进表示,一些证明方法,作时空性能分布图,34,算法分析的目的,算法分析(analysis of algorithms)是对一个算法需要多少计算时间和存储空间作定量的分析。,确定算法在什么样的环境下能够有效地运行。,分析在最好、最坏和平均情况下的执行情况。,对同一问题不同算法的有效性作出比较。,35,算法运行假定的计算机类型,要求独立于具体的软硬件环境单纯分析算法。,假定使用一台通用计算机,顺序处理每条指令；,存储容量足够大；,存取时间恒定。,/,第,1,次课程,36,第二章作业,证明：,n,2,O,(,n,3,),；,证明：,2,n,2,11,n,10,O,(,n,2,),；,证明：,O,的以下两个性质成立，其中,c,是一个正常数：,O,(,f,(,n,),O,(,g,(,n,),O,(,f,(,n,),g,(,n,),；,O,(,cf,(,n,),O,(,f,(,n,),；,证明：,n,3,O,(,n,2,),；,37,判断以下命题是否成立，假设成立，证明之；不成立，举反例。,5.如果g(n)(f(n)，那么(f(n)(g(n)(f(n)；？,6.(cf(n)(f(n)，其中c是一个正常数；？,7.f(n)(f(n)；？,8.(f(n)(g(n)(min(f(n),g(n)；？,9.(f(n)(g(n)(max(f(n),g(n)；？,10.(f(n)(g(n)(f(n)g(n)；？,38,算法分析过程,确定算法所涉及的运算,分析算法语句的执行次数,分析算法的执行时间的渐进表示,确定出能反映算法在各种情况下工作的数据集,作时空性能分布图,事前分析,准备工作,事后测试,全面分析的两个阶段,39,准备工作,(,一,),首先确定使用哪些运算以及执行这些运算所用的时间。,根本运算,由一些更根本的任意长序列的运算所组成的复杂运算,40,根本运算,时间囿界于常数的运算,加、减、乘、除整数算术运算,浮点算术、字符比较、对变量赋值、过程调用等,每种运算所用时间虽然不同，但都只花费一个固定量的时间,41,复杂运算,由一些更根本的任意长序列的运算组成,如：两个字符串的比较运算,一系列字符比较指令,一个字符的比较时间囿界于常数,字符串比较的时间总量那么取决于字符串的长度,42,准备工作,(,二,),其次是要确定出能反映算法在各种情况下工作的数据集。,编造出能产生,最好,、,最坏,和,有代表性,情况的数据配置,通过使用这些数据来运行算法，以更了解算法的性能。,算法分析最重要和最富于创造性的工作。,43,全面分析算法的两个阶段,事前分析,(a prior analysis),确定每条语句的执行次数。,求出该算法的一个,时间限界函数,(,一些关于参数的函数,),事后测试,(a posterior testing),收集此算法的实际执行时间和占用空间的统计资料,44,算法的执行时间,同一条语句在一个算法中的执行次数,(,frequency count,),称为频率计数,语句的时间总量,频率计数,执行一次该语句所需要的时间,算法的执行时间就是构成算法的所有语句的执行时间总量之和,由算法就可直接确定，,与所用的机器无关，且独立于程序设计语言。,依赖机器、程序设计语言、编译程序,45,例：计算语句,x,x,y,在下面三个程序段中的频率计数,begin,x,x,y,end,FC:1,begin,for,i,1 to,n,do,x,x,y,end,FC:,n,begin,for,i,1 to,n,do,for,j,1 to,n,do,x,x,y,end,FC:,n,2,语句的数量级是指执行它的频率计数之和,算法的数量级是指算法的所有语句的执行频率之和,确定一个算法的数量级十分重要，因为它在本质上,反映了算法所需的计算时间。,46,计算时间的根本特性,描述算法数量级的多项表达式,最高次项,最高次项的系数,最高次项的次数,准确分析出算法数量级的多项式表达式是很困难的，,因此我们对事前分析的计算时间进行渐进表示。,47,时间复杂性的形式化定义,算法的时间复杂性表示为,T,(,n,),，其中,n,是问题的规模。,最坏情况,下：,T,max,(,n,),max,T,(I)|size(I),n,最好情况,下：,T,min,(,n,),min,T,(I)|size(I),n,平均情况,下：,T,avg,(,n,),P,(I),T,(I),其中,I,是问题规模为,n,的实例，,p,(I),是实例,I,出现的概率。,size,(I),n,48,计算时间的渐进表示,定义,2.1,：,f,(,n,),O,(,g,(,n,),定义,2.2,：,f,(,n,),(,g,(,n,),定义,2.3,：,f,(,n,),(,g,(,n,),定理,2.1,49,f,(,n,),表示算法的计算时间,n,表示问题的规模,输入或输出量；,两者之和；,其中之一的某种测度。,g,(,n,),是在事前分析中确定的某个形式简单的函数,变量和函数的含义,f,(,n,),与机器和语言有关，而,g,(,n,),是独立于机器和语言的。,50,定义,2.1,如果存在两个正常数c和n0，对于所有的n n0，有|f(n)|c|g(n)|，那么记做f(n)O(g(n).,当,n,充分大时，,f,(,n,),有上界，一个常数倍的,g,(,n,),是,f,(,n,),的一个上界，,f,(,n,),的数量级就是,g,(,n,),。,f,(,n,),的阶不高于,g,(,n,),的阶。,在确定,f,(,n,),的数量级时，总是试图求出,最小的,g,(,n,),。,有关证明中，找出,c,和,n,0,是关键。,51,例子,判断,f,(,n,),O,(,g,(,n,),？,f,(,n,),3,n,g,(,n,),4,n,f,(,n,),n,1024,g,(,n,),1025,n,f,(,n,),2,n,2,11,n,10,g,(,n,),n,2,f,(,n,),n,2,g,(,n,),n,3,反例：,f,(,n,),n,3,g,(,n,),5,n,2,52,O,性质,对于非负的f(n)和g(n)，根据定义2.1，有如下性质：,1.O(f(n)O(g(n)O(max(f(n),g(n);,2.O(f(n)O(g(n)O(f(n)g(n)；,3.O(f(n)O(g(n)O(f(n)g(n)；,4.如果g(n)O(f(n)，那么O(f(n)O(g(n)O(f(n)；,5.O(cf(n)O(f(n)，其中c是一个正的常数；,6.f(n)O(f(n)。,53,定理,2.1,假设A(n)amnm a1na0是一个m次多项式，那么A(n)O(nm),证明：取,n,0,1,，当,n,n,0,时,由,A(,n,),的定义和不等式关系,|A,B|,|A|,|B|,有,|A(,n,)|,|,a,m,n,m,a,1,n,a,0,|,|,a,m,|,n,m,|,a,1,|,n,|,a,0,|,(|,a,m,|,|,a,m,1,|,n,|,a,0,|,n,m,),n,m,(|,a,m,|,|,a,m,1,|,|,a,0,|),n,m,取,c,|,a,m,|,|,a,m,1,|,|,a,0,|,，有,|A(,n,)|,cn,m,即：,A(,n,),O,(,n,m,),，定理得证。,54,定理2.1说明，变量n的最高阶数为m的任一多项式，与nm同阶。因此一个计算时间为m阶多项式的算法，其时间都可以用O(nm)来表示。,假设一个算法有数量级为c1nm1，c2nm2，cknmk的k个语句，那么算法的数量级及计算时间就是,c1nm1c2nm2 cknmkO(nm),其中 m maxmi|1 i k,假设A(n)amnm a1na0是一个m次多项式，那么A(n)O(nm),55,从计算时间上对算法分类,多项式时间算法,(polynomial time algorithm),：,用多项式来对其计算时间限界的算法,O,(1),O,(log,n,),O,(,n,),O,(,n,log,n,),O,(,n,2,),O,(,n,3,),指数时间算法,(exponential time algorithm),：,计算时间用指数函数限界的算法,O,(2,n,),O,(,n,),O,(,n,n,),数量级对算法有效性的影响,56,不同时间复杂性函数的比照,57,小规模数据,58,中等规模数据,59,定义2.2 如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|，那么记做f(n)(g(n).,当,n,充分大时，,f,(,n,),有下界，一个常数倍的,g,(,n,),是,f,(,n,),的一个下界。,f,(,n,),的阶不低于,g,(,n,),的阶。,在确定,f,(,n,),的下界时，总是试图求出,最大的,g,(,n,),。,有关证明中，找出,c,和,n,0,是关键。,60,性质,对于非负的f(n)和g(n)，根据定义2.2，有如下性质：,1.(f(n)(g(n)(min(f(n),g(n);,2.(f(n)(g(n)(f(n)g(n)；,3.(f(n)(g(n)(f(n)g(n)；,4.如果g(n)(f(n)，那么(f(n)(g(n)(f(n)；,5.(cf(n)(f(n)，其中c是一个正的常数；,6.f(n)(f(n)。,61,定义2.3 如果存在两个正常数c1,c2和n0，对于所有的n n0，有 c1|g(n)|f(n)|c2|g(n)|，那么记作：f(n)(g(n).,一个算法的,f,(,n,),(,g,(,n,),意味着该算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。,/,第,2,次课程,62,渐近表示函数的假设干性质,1传递性,f(n)(g(n)，g(n)(h(n)f(n)(h(n)；,f(n)O(g(n)，g(n)O(h(n)f(n)O(h(n)；,f(n)(g(n)，g(n)(h(n)f(n)(h(n)；,2反身性,f(n)(f(n)；f(n)O(f(n)；f(n)(f(n)；,3对称性,f(n)(g(n)g(n)(f(n)；,4互对称性,f(n)O(g(n)g(n)(f(n).,63,5算术运算,O(f(n)O(g(n)O(maxf(n),g(n)；,O(f(n)O(g(n)O(f(n)g(n)；,O(f(n)O(g(n)O(f(n)g(n)；,O(cf(n)O(f(n)；,f(n)O(g(n)O(f(n)O(g(n)O(g(n)。,、也有类似性质，证明方法类似。,渐近表示函数的假设干性质,64,规那么O(f(n)O(g(n)O(maxf(n),g(n)的证明：,对于任意f1(n)O(f(n)，存在正常数c1和自然数n1，使得对所有,n n1，有f1(n)c1f(n)。,类似地，对于任意g1(n)O(g(n)，存在正常数c2和自然数n2，,使得对所有n n2，有g1(n)c2g(n)。,令c3 maxc1,c2，n3 maxn1,n2，h(n)maxf(n),g(n)。,那么对所有的 n n3，有,f1(n)g1(n)c1f(n)c2g(n),c3f(n)c3g(n)c3(f(n)g(n),2c3 maxf(n),g(n),2c3h(n)O(maxf(n),g(n).,65,规那么O(f(n)O(g(n)O(f(n)g(n)的证明：,对于任意f1(n)O(f(n)，存在正常数c1和自然数n1，使得对所有,n n1，有f1(n)c1f(n)。,类似地，对于任意g1(n)O(g(n)，存在正常数c2和自然数n2，,使得对所有n n2，有g1(n)c2g(n)。,令c3 maxc1,c2，n3 maxn1,n2，h(n)f(n)g(n)。,那么对所有的 n n3，有,O(f(n)O(g(n)f1(n)g1(n),c1f(n)c2g(n),c3f(n)c3g(n),c3(f(n)g(n),c3h(n)O(f(n)g(n).,66,规那么O(f(n)O(g(n)O(f(n)g(n)的证明：,对于任意f1(n)O(f(n)，存在正常数c11和自然数n1，,使得对所有 n n1，有f1(n)c1f(n)。,类似地，对于任意g1(n)O(g(n)，存在正常数c2 1和自然数n2，,使得对所有n n2，有g1(n)c2g(n)。,令c3 c1 c2，n3 maxn1,n2，h(n)f(n)g(n)。,那么对所有的 n n3，有,O(f(n)O(g(n)f1(n)g1(n)c1f(n)c2g(n),c3f(n)g(n),c3h(n),O(f(n)g(n).,67,数学根底,1常用的整数求和公式,通式,68,算法渐近复杂性分析中常用函数,2单调函数,单调递增：m n f(m)f(n);,单调递减：m n f(m)f(n);,严格单调递增：m n f(m)f(n);,严格单调递减：m n f(m)f(n).,3取整函数,x ：不大于x的最大整数；2.5 2 2 2,x ：不小于x的最小整数。2.5 3 2 2,69,取整函数的假设干性质,x,1 ,x,x,x,x,1,；,n,/2,n,/2 ,n,;,对于,n,0,，,a,b,0,，有：,n,a,b,n,ab,;,n,a,b,n,ab,;,a,b,(,a,(,b,1),b,;,a,b,(,a,(,b,1),b,;,f,(,x,),x,g,(,x,),x,为,单调递增函数。,70,4多项式函数,p(n)a0 a1n a2n2 adnd；ad0;,p(n)(nd);,p(n)O(nk)p(n)多项式有界；,p(n)O(1)p(n)c;,71,指数函数一些性质,对于正整数,m,n,和实数,a,0:,a,0,1;,a,1,a,;,a,-1,1/,a,;,(,a,m,),n,a,mn,;,(,a,m,),n,(,a,n,),m,;,a,m,a,n,a,m+n,;,a,1,a,n,为,单调递增函数,;,a,1,n,b,o,(,a,n,),72,e,x,1+,x,;,|x|,1 1,x,e,x,1,x,x,2,;,e,x,1,x,(,x,2,),as,x,0;,73,log,n,log,2,n,;,lg,n,log,10,n,;,ln,n,log,e,n,;,log,k,n,(log,n,),k,;,log log,n,log(log,n,);,for,a,0,b,0,c,0,5对数函数,74,75,|,x,|1,for,x,1,for any,a,0,log,b,n,O,(,n,a,),76,6阶乘函数,Stirlings approximation,77,78,一些数学证明方法,直接证明：PQ,间接证明：,反证法,举反例,数学归纳法：,初始归纳：i1 结论成立；,归纳假设：假设in1时成立；,归纳证明：证明in时成立。,79,时空分布图,事后测试是在对算法进行设计、确认、事前分析和调试之后要做的工作，以确定程序所消耗的精确时间和空间，即作时空性能分布图。与所用计算机密切相关。,以时间分布图为例，要求：,时钟及其精确度 操作系统的工作方式,解决因时钟误差引起的噪声问题，推荐两种方法：,增加输入规模 增加执行次数,时空分布图的做法,用途,比较同一问题的不同算法,对算法改进前后进行比较,80,主要内容,2.1 算法,2.2 分析算法及数学根底,2.3 用SPARKS语言写算法,2.4 根本数据结构,81,2.3,用,SPARKS,语言写算法,SPARKS语言的根本数据类型：,整型(integer),实型(real),布尔型(boolean),字符型(char),SPARKS语言的变量命名规那么：,以字母开头，不允许使用特殊字符，不允许与保存字重复,赋值语句：,变量,表达式,逻辑运算符：,and,or,not,关系运算符：,，,，,，,，,，,布尔值,:true,，,false,数组：任意整数下界和上界的多维数组,integer A(,l,1,:,u,1,l,n,:,u,n,);,例,:integer,x,y,;char,ch,;,例,:integer A(1:10);real B(3:6,1:4);,82,SPARKS,语言的条件语句,if,条件,then s1,endif,if,条件,then s1 else s2,endif,case,:,条件,1,:s,1,:,条件,n,:s,n,:,else,:s,n,1,endcase,SPARKS,语言的,case,语句,2.3,用,SPARKS,语言写算法,83,SPARKS,语言的循环语句,while,条件,do,S,repeat,loop,S,until,条件,repeat,for,变量,初值,to,终值,by,变量增值,do,S,repeat,2.3,用,SPARKS,语言写算法,84,exit,转到含有,exit,的最内层循环语句后面的第一条语句,goto,标号,cycle,结束本次循环,return,stop,2.3,用,SPARKS,语言写算法,85,SPARKS,语言的函数,(,过程,),procedure NAME(),S,return(),end NAME,函数名,通常用大写字母,说明参数的数据类型,和函数中使用的变量,parameters,形式参数,global,全局变量,local,局部变量,函数的语句局部,SPARKS语言的输入、输出：,read参数表；print参数表；,2.3,用,SPARKS,语言写算法,86,procedure MAX(,A,n,j,),parameters real,A,(1:,n,);,parameters integer,n,j,;,real,xmax,;,local integer,i,;,xmax,A(1);,for,i,2 to,n,do,if,A,(,i,),xmax,then,xmax,A,(,i,);,j,i,;,endif,repeat,return(,xmax,);,end MAX,同质异相,2.3,用,SPARKS,语言写算法,global,xmax,integer,i,j,n,87,栈和队列,树,集合的树表示和不相交集合的合并,图,2.4 根本数据结构,88,小结,算法的五个重要特性,确定性、可行性、输入、输出、有穷性,算法分析的根本概念和思想,算法时间复杂度的渐进表示,了解意义、会使用、能推导证明性质,89,第二章作业,证明：,n,2,O,(,n,3,),；,证明：,2,n,2,11,n,10,O,(,n,2,),；,证明：,O,的以下两个性质,O,(,f,(,n,),O,(,g,(,n,),O,(,f,(,n,),g,(,n,),；,O,(,cf,(,n,),O,(,f,(,n,),，其中,c,是一个正的常数；,证明：,n,3,O,(,n,2,),；,90,5.,如果,g,(,n,),(,f,(,n,),，则,(,f,(,n,),(,g,(,n,),(,f,(,n,),；,?,6.,(,cf,(,n,),(,f,(,n,),，其中,c,是一个正的常数,;,？,7.f,(,n,),(,f,(,n,)?,8.,(,f,(,n,),(,g,(,n,),(min(,f,(,n,),g,(,n,)?,9.,(,f,(,n,),(,g,(,n,),(max(,f,(,n,),g,(,n,)?,10.,(,f,(,n,),(,g,(,n,),(,f,(,n,),g,(,n,)?,若成立，证明之；不成立，举反例。,