2算法第二章导引详解

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,其次章 导引与根本数据构造,名目,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是问题的规模。,最坏状况下：Tmax(n)=max T(I)|size(I)=n,最好状况下：Tmin(n)=min T(I)|size(I)=n,平均状况下：Tavg(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和n0，对于全部的nn0，,有|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)=amnm+a1n+a0是一个m次多项式，,则A(n)=O(nm)。,证明：取,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的任一多项式，与nm同阶。因此一个计算时间为m阶多项式的算法，其时间都可以用O(nm)来表示。,假设一个算法有数量级为c1nm1，c2nm2，cknmk的,k个语句，则算法的数量级及计算时间就是,c1nm1+c2nm2+cknmk=O(nm),其中 m=maxmi|1 i k,定理2.1：假设A(n)=amnm+a1n+a0是一个m次多,项式，则A(n)=O(nm)。,数量级对算法有效性的影响,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,证明:n2=O(n3);,证明:2n2+11n-10=O(n2);,证明：O的以下两共性质,O(f(n)O(g(n)=O(f(n)g(n);,O(cf(n)=O(f(n)，其中c是一个正的常数；,证明：n3O(n2),作业,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,)?,若成立，证明之；不成立，举反例。,课程之外,授人以鱼不如授人以渔,开阔我们的思路,对我们进展很好的思维训练,方法永久拥有理性的特点,你见，或者不见我，我就在那里，不悲不喜。你念，或者不念我，情就在那里，不来不去。你爱，或者不爱我，爱就在那里，不增不减。你跟，或者不跟我，我的手就在你手里，不舍不弃。来我的怀里，或者，让我住进你的心里。默然 相爱，安静 欢快。见与不见 扎西拉姆多多,你来，或者不来上课，教室就在这里，不悲不喜。你迟到，或者不迟到，我就在这里，不来不去。你学，或者不爱学，学问就在这里，不增不减。你考好，或者考不好，你的卷子就在我的手里，,不舍不弃。通过，或者，不通过。庆幸，默然，欢快，懊恼。,