算法导引详解课件

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 导引与基本数据结构,目录,2.1,算法,2.2,分析算法,2.3,用,SPARKS,语言写算法,2.4,基本数据结构,(,略,),2.1,算 法,什么是算法,算法的重要特性,计算过程与算法的区别,问题的求解过程,算法学习的基本内容,什么是算法,算法是解决一确定类问题的任意一种,特殊,的方法。,数值计算方法,非数值计算方法,算法的非形式描述：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。,求解数值问题，插值计算、数值积分等。,求解非数值问题，主要进行判断比较。,算法,(Algorithm),的五个重要特性,确定性,：每一种运算必须要有确切定义，无二义性。,例如：,(1)5/0,；,(2)6,或,7,与,x,相加。,能行性,：运算都是基本运算，原理上能,由人用纸和,笔,在有限时间完成。,输 入,：有,0,个或多个输入。,输 出,：一个或多个输出。,有穷性,：在执行了有穷步运算后终止。,仅仅有穷还不够，还要在现代计算机上有效才行。,计算过程与算法的区别,计算过程可以不满足算法的性质,(5),有穷性。,例如操作系统，当没有任务时，操作系统并不终止，而是处于等待状态，直到有新的任务启动，因而不是一个算法。,程序,=,算法,+,数据结构,(By Niklaus Wirth,),问题的求解过程,证明正确性,分析算法,理解问题,选择数据结构和,算法设计策略,设计算法,设计程序,算法学习的基本内容,如何设计算法,如何表示算法,如何确认算法,如何分析算法,如何测试程序,如何设计算法,面对具体问题，,运用一些基本设计策略,被实践证明是有用的一些基本设计策略,计算机科学、运筹学、电器工程等领域,设计出很多精致有效的好算法,掌握这些策略，设计出更多的好算法,如何表示算法,设计的算法要用恰当的方式地表示出来,采用结构程序设计的方式,SPARKS,程序设计语言,简单明了,如何确认算法,算法确认,(algorithm validation),证明该算法对所有可能的合法输入，都能给出正确答案,算法确认的目的,确保该算法能正确无误地工作,穷举法,推理,数学归纳法、反证法,构造性证明,测试,如何分析算法,分析执行一个算法时，,占用,CPU,时间完成运算；,占用存储器的存储空间，存放程序和数据。,既对一个算法需要多少计算时间和存储空间，做定量分析。,如何测试程序,调试,调试只能指出有错误，而不能指出它们不存在错误。,源于程序正确性的证明还没有取得突破性进展。,时空分布图,用各种给定数据执行调试后的程序,测定计算时间和空间,印证之前的分析是否正确,指出实现最优化的有效逻辑位置,2.2,分析算法,算法分析目的,算法分析的准备工作,计算时间的渐进表示,一些证明方法,作时空性能分布图,算法分析的目的,算法分析,(analysis of algorithms),是对一个算法需要多少,计算时间,和,存储空间,作定量的分析。,确定算法在什么样的环境下能够有效地运行。,分析在,最好,、,最坏,和,平均,情况下的执行情况。,对同一问题不同算法的有效性作出比较。,时间复杂性的形式化定义,算法的时间复杂性,T,(,n,),；,算法的空间复杂性,S,(,n,),；,其中,n,是问题的规模。,最坏情况,下：,T,max,(,n,)=max,T,(I)|size(I)=,n,最好情况,下：,T,min,(,n,)=min,T,(I)|size(I)=,n,平均情况,下：,T,avg,(,n,)=,其中,I,是问题的规模为,n,的实例，,p,(I),是实例,I,出现的概率。,算法运行假定的计算机类型,要求独立于具体的软硬件环境单纯分析算法。,假定使用一台通用计算机,顺序处理每条指令；,存储容量足够大；,存取时间恒定。,算法分析过程,确定算法所涉及的运算,分析算法语句的执行次数,分析算法的执行时间的渐进表示,确定出能反映算法在各种情况下工作的数据集,作时空性能分布图,事前分析,准备工作,事后测试,全面分析的两个阶段,准备工作,(,一,),首先确定使用哪些,运算,以及执行这些运算所用的时间。,基本运算,由一些更基本的任意长序列的运算所组成的复杂运算,基本运算,时间囿界于常数的运算,加、减、乘、除整数算术运算,浮点算术、字符比较、对变量赋值、过程调用等,每种运算所用时间虽然不同，但都只花费一个固定量的时间,复杂运算,由一些更基本的任意长序列的运算组成,如：两个字符串的比较运算,一系列字符比较指令,一个字符的比较时间,囿界于常数,字符串比较的时间总量则取决于字符串的长度,准备工作,(,二,),其次是要确定出能反映算法在各种情况下工作的数据集。,编造出能产生,最好,、,最坏,和,有代表性,情况的数据配置,通过使用这些数据来运行算法，以更了解算法的性能。,算法分析最重要和最富于创造性的工作。,全面分析算法的两个阶段,事前分析,(a priori analysis),确定每条语句的执行次数。,求出该算法的一个,时间限界函数,(,一些,关于参数的函数,),。,事后测试,(a posterior testing),作时空性能分布图。,算法的执行时间,同一条语句在一个算法中的执行次数,(,frequency count,),称为频率计数,语句的时间总量,=,频率计数,执行一次该语句所需要的时间,算法的执行时间就是构成算法的所有语句的执行时间总量之和,由算法就可直接确定，,与所用的机器无关，且独立于程序设计语言。,依赖机器、程序设计语言、编译程序,例：计算语句,x,z+y,在下面三个程序段中的频率计数,begin,x,z+y,end,FC:1,begin,for i,1 to n do,x,z+y,end,FC:n,begin,for i,1 to n do,for j,1 to n do,x,z+y,end,FC:n,2,语句的数量级,是指执行它的频率,算法的数量级,是指算法的所有语句的执行频率之和,确定一个算法的数量级十分重要，因为它在本质上,反映了算法所需的计算时间。,算法的数量级,计算时间的基本特性,描述算法数量级的多项表达式,最高次项,最高次项的系数,最高次项的次数,准确分析出算法数量级的多项式表达式是很困难的，,因此我们对事前分析的计算时间进行渐进表示。,计算时间的渐进表示,定义,2.1,：,f(n)=O(g(n),定义,2.2,：,f(n)=(g(n),定义,2.3,：,f(n)=(g(n),定理,2.1,变量和函数的含义,n,表示问题规模，,输入或输出量；,两者之和；,其中之一的某种测度。,f(n),表示算法的计算时间。,g(n),是在事前分析中确定的某个形式简单的函数。,f(n),与机器和语言有关，而,g(n),是独立于机器和语言的。,定义,2.1,如果存在两个正常数,c,和,n,0,，对于所有的,nn,0,，,有,|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,是关键。,判断,f(n),O(g(n),？,f(n),3n,g(n)=n,f(n),n+1024,g(n)=1025n,f(n),2n,2,+11n-10,g(n)=3n,2,f(n),n,2,g(n)=,n,3,f(n),n,3,g(n)=,n,2,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,),。,定理,2.1,若,A(n)=a,m,n,m,+a,1,n+a,0,是一个,m,次多项式，,则,A(n)=O(n,m,),。,证明：取,n,0,=1,，当,nn,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)|c n,m,即：,A(n)=O(n,m,),，定理得证。,定理,2.1,表明，变量,n,的最高阶数为,m,的任一多项式，与,n,m,同阶。因此一个计算时间为,m,阶多项式的算法，其时间都可以用,O(n,m,),来表示。,若一个算法有数量级为,c,1,n,m1,，,c,2,n,m2,，,c,k,n,mk,的,k,个语句，则算法的数量级及计算时间就是,c,1,n,m1,+c,2,n,m2,+c,k,n,mk,=O(n,m,),其中,m=maxm,i,|1 i k,定理,2.1,：若,A(n)=a,m,n,m,+a,1,n+a,0,是一个,m,次多,项式，则,A(n)=O(n,m,),。,数量级对算法有效性的影响,P25-26,从计算时间上算法可以分为两类：,多项式时间算法,(polynomial time algorithm):,用多项式来对其计算时间限界的算法,O(1)O(logn)O(n)O(nlogn)O(n,2,)O(n,3,),指数时间算法,(exponential time algorithm):,计算时间用指数函数限界的算法,O(2,n,)O(n!),数据集与时间复杂度有关,时钟不准确造成的噪声,增大规模,重复执行,2.3,用,SPARKS,语言写算法,P28-33,作业,1,证明,:,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,),作业,1,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,)?,若成立，证明之；不成立，举反例。,课程之外,授人以鱼不如授人以渔,开阔我们的思路,对我们进行很好的思维训练,方法永远拥有理性的特点,你见，或者不见我，我就在那里，不悲不喜。你念，或者不念我，情就在那里，不来不去。你爱，或者不爱我，爱就在那里，不增不减。你跟，或者不跟我，我的手就在你手里，不舍不弃。来我的怀里，或者，让我住进你的心里。默然 相爱，寂静 欢喜。,见与不见,扎西拉姆,多多,你来，或者不来上课，教室就在这