算法第二章导引详解.ppt

《算法第二章导引详解.ppt》由会员分享，可在线阅读，更多相关《算法第二章导引详解.ppt（47页珍藏版）》请在三一办公上搜索。

1、第二章 导引与基本数据结构,目录,2.1 算法2.2 分析算法2.3 用SPARKS语言写算法2.4 基本数据结构(略),2.1 算 法,什么是算法算法的重要特性计算过程与算法的区别问题的求解过程算法学习的基本内容,什么是算法,算法是解决一确定类问题的任意一种特殊的方法。数值计算方法非数值计算方法算法的非形式描述：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。,求解数值问题，插值计算、数值积分等。,求解非数值问题，主要进行判断比较。,算法(Algorithm)的五个重要特性,确定性：每一种运算必须要有确切定义，无二义性。例如：(1)5/0；(2)6或7与x相加。能行性：运算

2、都是基本运算，原理上能由人用纸和 笔在有限时间完成。输 入：有0个或多个输入。输 出：一个或多个输出。有穷性：在执行了有穷步运算后终止。,仅仅有穷还不够，还要在现代计算机上有效才行。,计算过程与算法的区别,计算过程可以不满足算法的性质(5)有穷性。例如操作系统，当没有任务时，操作系统并不终止，而是处于等待状态，直到有新的任务启动，因而不是一个算法。程序=算法+数据结构(By Niklaus Wirth),问题的求解过程,算法学习的基本内容,如何设计算法如何表示算法如何确认算法如何分析算法如何测试程序,如何设计算法,面对具体问题，运用一些基本设计策略被实践证明是有用的一些基本设计策略计算机科学、

3、运筹学、电器工程等领域设计出很多精致有效的好算法掌握这些策略，设计出更多的好算法,如何表示算法,设计的算法要用恰当的方式地表示出来采用结构程序设计的方式SPARKS程序设计语言简单明了,如何确认算法,算法确认(algorithm validation)证明该算法对所有可能的合法输入，都能给出正确答案算法确认的目的确保该算法能正确无误地工作穷举法推理数学归纳法、反证法构造性证明测试,如何分析算法,分析执行一个算法时，占用CPU时间完成运算；占用存储器的存储空间，存放程序和数据。既对一个算法需要多少计算时间和存储空间，做定量分析。,如何测试程序,调试调试只能指出有错误，而不能指出它们不存在错误。源

4、于程序正确性的证明还没有取得突破性进展。时空分布图用各种给定数据执行调试后的程序测定计算时间和空间印证之前的分析是否正确指出实现最优化的有效逻辑位置,2.2 分析算法,算法分析目的算法分析的准备工作计算时间的渐进表示一些证明方法作时空性能分布图,算法分析的目的,算法分析(analysis of algorithms)是对一个算法需要多少计算时间和存储空间作定量的分析。确定算法在什么样的环境下能够有效地运行。分析在最好、最坏和平均情况下的执行情况。对同一问题不同算法的有效性作出比较。,时间复杂性的形式化定义,算法的时间复杂性T(n)；算法的空间复杂性S(n)；其中n是问题的规模。,最坏情况下：T

5、max(n)=max T(I)|size(I)=n 最好情况下：Tmin(n)=min T(I)|size(I)=n 平均情况下：Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。,算法运行假定的计算机类型,要求独立于具体的软硬件环境单纯分析算法。假定使用一台通用计算机顺序处理每条指令；存储容量足够大；存取时间恒定。,算法分析过程,确定算法所涉及的运算,分析算法语句的执行次数,分析算法的执行时间的渐进表示,确定出能反映算法在各种情况下工作的数据集,作时空性能分布图,事前分析,准备工作,事后测试,全面分析的两个阶段,准备工作(一),首先确定使用哪些运算以及执行这些运算所用

6、的时间。基本运算由一些更基本的任意长序列的运算所组成的复杂运算,基本运算,时间囿界于常数的运算加、减、乘、除整数算术运算浮点算术、字符比较、对变量赋值、过程调用等每种运算所用时间虽然不同，但都只花费一个固定量的时间,复杂运算,由一些更基本的任意长序列的运算组成如：两个字符串的比较运算一系列字符比较指令一个字符的比较时间囿界于常数字符串比较的时间总量则取决于字符串的长度,准备工作(二),其次是要确定出能反映算法在各种情况下工作的数据集。编造出能产生最好、最坏和有代表性情况的数据配置通过使用这些数据来运行算法，以更了解算法的性能。,算法分析最重要和最富于创造性的工作。,全面分析算法的两个阶段,事前

7、分析(a priori analysis)确定每条语句的执行次数。求出该算法的一个时间限界函数(一些关于参数的函数)。事后测试(a posterior testing)作时空性能分布图。,算法的执行时间,同一条语句在一个算法中的执行次数(frequency count)称为频率计数语句的时间总量=频率计数执行一次该语句所需要的时间算法的执行时间就是构成算法的所有语句的执行时间总量之和,由算法就可直接确定，与所用的机器无关，且独立于程序设计语言。,依赖机器、程序设计语言、编译程序,例：计算语句xz+y在下面三个程序段中的频率计数,beginxz+yendFC:1,beginfor i1 to n

8、 doxz+yendFC:n,beginfor i1 to n do for j1 to n doxz+yendFC:n2,语句的数量级是指执行它的频率算法的数量级是指算法的所有语句的执行频率之和,确定一个算法的数量级十分重要，因为它在本质上反映了算法所需的计算时间。,算法的数量级,计算时间的基本特性,描述算法数量级的多项表达式最高次项最高次项的系数最高次项的次数,准确分析出算法数量级的多项式表达式是很困难的，因此我们对事前分析的计算时间进行渐进表示。,计算时间的渐进表示,定义2.1：f(n)=O(g(n)定义2.2：f(n)=(g(n)定义2.3：f(n)=(g(n)定理2.1,变量和函数的

9、含义,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和n0是关键。,判断f(n)O(g(n)？,f(n)3n,g(n)=

10、nf(n)n+1024,g(n)=1025nf(n)2n2+11n-10,g(n)=3n2f(n)n2,g(n)=n3f(n)n3,g(n)=n2,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是一个

11、m次多项式，则A(n)=O(nm)。,证明：取n0=1，当nn0时 由A(n)的定义和不等式关系|A+B|A|+|B|有|A(n)|=|amnm+a1 n+a0|am|nm+|a1|n+|a0|=(|am|+|am-1|/n+|a0|/nm)nm(|am|+|am-1|+|a0|)nm取 c=|am|+|am-1|+|a0|，有|A(n)|c nm即：A(n)=O(nm)，定理得证。,定理2.1表明，变量n的最高阶数为m的任一多项式，与nm同阶。因此一个计算时间为m阶多项式的算法，其时间都可以用O(nm)来表示。,若一个算法有数量级为c1nm1，c2nm2，cknmk的 k个语句，则算法的数量

12、级及计算时间就是 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(n2)O(n3),指数时间算法(exponential time algorithm):计算时间用指数函数限界的算法 O(2n)O(n!)O(nn),不同时间复杂性函数的对比,定义2.2,

13、当n充分大时，f(n)有下界，一个常数倍的g(n)是f(n)的一个下界。f(n)的阶不低于g(n)的阶。在确定f(n)的下界时，总是试图求出最大的g(n)。有关证明中，找出c和n0是关键。,如果存在两个正常数c和n0，对于所有的nn0，有|f(n)|c|g(n)|，则记作：f(n)=(g(n)。,性质,对于非负的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)

14、=(f(n)，其中c是一个正的常数；6.f(n)=(f(n)。,定义2.3,一个算法的f(n)=(g(n)意味着该算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。,如果存在正常数c1,c2和n0，对于所有的nn0，有c1|g(n)|f(n)|c2|g(n)|，则记作：f(n)=(g(n)。,渐近表示函数的若干性质,传递性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)；反身性f(n)=(f(n)；f(n)=O(f(n)；f(n)=

15、(f(n)。,常用的整数求和公式,通式：,一些数学证明方法,直接证明：PQ间接证明：反证法举反例数学归纳法：初始归纳：i=1 结论成立；归纳假设：若i=n-1时成立；归纳证明：证明i=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

16、);O(cf(n)=O(f(n)，其中c是一个正的常数；证明：n3O(n2),作业15.如果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)?若成立，证明之；不成立，举反例。,课程之外,授人以鱼不如授人以渔开阔我们的思路,对我们进行很好的思维训练方法永远拥有理性的特点,你见，或者不见我，我就在那里，不悲不喜。你念，或者不念我，情就在那里，不来不去。你爱，或者不爱我，爱就在那里，不增不减。你跟，或者不跟我，我的手就在你手里，不舍不弃。来我的怀里，或者，让我住进你的心里。默然 相爱，寂静 欢喜。见与不见 扎西拉姆多多,你来，或者不来上课，教室就在这里，不悲不喜。你迟到，或者不迟到，我就在这里，不来不去。你学，或者不爱学，知识就在这里，不增不减。你考好，或者考不好，你的卷子就在我的手里，不舍不弃。通过，或者，不通过。庆幸，默然，欢喜，懊恼。,