数据结构第2章.ppt
《数据结构第2章.ppt》由会员分享,可在线阅读,更多相关《数据结构第2章.ppt(38页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第二章第二章 程序设计基本策略与方法程序设计基本策略与方法n 学习目标:学习目标:n算法的基本概念n算法的复杂度分析与度量n穷举法n递推法与迭代法n递归法n逐步求精法n分治法2.1 算法的基本概念算法的基本概念2.1.1算法的概念算法的概念算法:算法:通俗而言,就是解决给定问题的方法。是规则的有穷序列,它为解决某一特定类型的问题规定了一个运算过程。具有下列特性:有穷性:一个算法必须在执行有穷步之后结束。确定性:算法的每一步必须是确切定义的,对于每种情况,有待执行的每种动作必须严格地和清楚地规定。可行性:算法应该是可行的,它们都可由相应的基本计算装置所理解。输入:一个算法有零个或多个输入,它们是
2、在算法所需的初始量或被加工的对象的表示。这些输入取自特写的对象集合。输出:一个算法有一个或多个输出,它们是与输入有特定关系的。算法的描述方法n用自然语言,易产生歧义、繁琐、不被机器识别n使用程序流程图、N-S图等算法描述工具。其特点是描述过程简洁、明了。n用计算机语言描述,就是计算机程序。注意:1)计算机程序不一定就算一个算法:例如,操作系统,只要整个系统不遭破坏,它将永远不会停止。因此,操作系统不是一个算法。2)有些算法不能用计算机语言来描述:程序中的指令必须是机器可执行的,而算法中的指令则无此限制。什么是“好”的算法通常,从下列几个方面衡量算法的优劣:n正确性正确性。也称有效性,是指算法能
3、满足具体问题的要求。亦即对任何合法的输入,算法都会得出正确的结果。n可读性可读性。指算法被理解的难易程度。可读性实质上强调的是:越简单的东西越美。n健壮性健壮性(鲁棒性)(鲁棒性)。是指对非法输入的抵抗能力。它强调的是,如果输入非法数据,算法应能加以识别并做出处理,而不是产生误动作或陷入瘫痪。n高效高效(低时间复杂度与空间复杂度)。低时间复杂度与空间复杂度)。时间复杂度是指算法的运行的时间消耗,同一个问题,不同的算法可能有不同的时间复杂度。空间复杂度是指算法运行所需的存储空间的多少。2.1.2 算法时间复杂度算法时间复杂度n简单地讲,算法的时间复杂度是指算法的运行的时间消耗的大小,但这里的“运
4、行”并不是指在具体机上的运行。一个算法在具体计算机上的运行速度,不仅取决于算法本身,而且与目标计算机(运行算法的计算机)的速度有关。如果算法是用非目标指令(如汇编语言、高级语言等)描述的,则运行速度还与描述语言的编译器所生成的目标代码的质量(或解释器本身的质量)有关。n算法的时间复杂度指算法自身的抽象运行的时间消耗,与运行算法的目标计算机及描述算法的工具无关。只与算法本身以及问题的规模有关。时间复杂度相关因素算法的时间复杂度与下列因素有关:n问题性质:有的问题比较复杂,而有的比较简单;n问题规模:同一问题,同一算法,其处理的对象的规模不同,则耗时也不同;n算法性质:同一问题,不同的解决方法,效
5、率也不同。一个算法的时间复杂度通常用函数描述(时间复杂度函数)。时间复杂度函数通常可以描述为问题规模的函数。时间复杂度的渐进表示复杂度的渐进表示:复杂度的精确表示很困难,许多算法的时间复杂度函数不能以解析形式给出。所以通常用某些简单函数近似表示。常用的上界函数有:log(n),nm,an,n!,.下面给出几种常见的函数的比较关系:即当n充分大时,下列关系成立:O(a)O(log n)O(n)O(n.logn)O(n2).O(nm)O(an)O(n!)O(nn)上面,n为自变量,a和m为常数 算法的时间复杂度的分类n多项式时间复杂度算法:渐近函数为多项式,或变化率不超过多项式。n指数时间复杂度算
6、法:渐近函数变化率超过多项式,这类算法也称NP(nondeterministic polynomial)-困难的算法。2.1.3 算法时间复杂度的度量n语句频度语句频度(Frequency Count)是指语句被重复执行的次数。即对某语句,若在算法的一次运行中它被执行n次,则它的语句频度为n。n我们用算法中的各语句的语句频度算法中的各语句的语句频度之和之和表示算法的算法的时间复杂度时间复杂度例例 1.8 (1/2)考虑下列子程序,它的功能是求出考虑下列子程序,它的功能是求出数组数组a a中各数的中各数的大小次序号大小次序号,存入数组存入数组b b中的对应位置。例如,若中的对应位置。例如,若a=
7、4,2,3,9,6,8,7,a=4,2,3,9,6,8,7,则则程序结束后,数组程序结束后,数组b b内容为内容为 b=3,1,2,7,4,6,5,b=3,1,2,7,4,6,5,表示表示4 4,2 2,3 3,9 9,6 6,8 8,7 7的大小次序分别为的大小次序分别为3 3,1 1,2 2,7 7,4 4,6 6,5.5.void OrderNumbers(int*a,int n,int*b)int i,j;for(i=0;in;i+)bi=1;(1):nfor(i=0;in-1;i+)(2):n-1 for(j=i+1;jn;j+).(3):(n-i-1)if(ai aj).(4):(
8、n-i-1)bj+;.(5):(n-i-1)else bi+;return;例例 1.8 (2/2)总的语句频度最大为:n+(n-1)+3i=1n(n-i-1)=2n-1+3(n-1)n/2=3n2/2+7n/2 1=O(n2)2.1.4 空间复杂度空间复杂度(Space complexity)是指程序运行从开始到结束所需的存储量 程序运行所需的存储空间包括以下两部分:程序运行所需的存储空间包括以下两部分:固定部分。这部分空间与所处理数据的大小和个数无关,或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。可变部分。这部分空间大小与算法在某次执行中处理
9、的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。2.2 穷举法 穷举法穷举法(枚举法枚举法/试探法试探法)的基本思想是:的基本思想是:分别列举出各种可能解,测试(试探)其是否满足条件(是否是欲求的解),分别列举出各种可能解,测试(试探)其是否满足条件(是否是欲求的解),若是,则输出之。若是,则输出之。特点是算法简单,但是运算量大。当问题的规模变大,执行的的速度变慢。n例例2.2解不定方程。不定方程(组)是指独立方程个数少于变量个数而导致方程有多解。如,2x+3y=20是一个不定方程(设x,y为正整数)。解这个方程,就是求出所有
10、的解。不定方程一般都有限定条件,我们这里考虑正整数解的情况。解这个方程,一个简单的做法是,让x和y分别遍取0到20内的正整数,并代入方程计算,若值为20,则表示找到一组解。具体的程序片断如下。for(i=0;i=20;i+)for(j=0;j=20;j+)if(2*i+3*j=20)coutni,=0;z能被3整除)程序为:for(x=0;x=100;x+)for(y=0;y=100-x;y+)z=100-x-y;if(z%3=0&15*x+9*y+z=300)coutx yz=0;z被被3整除整除)程序为:for(x=0;x=14;x+)y=100-7*x;if(y%4)continue;e
11、lse y/=4;z=100-x-y;if(z%3)continue;coutx y zendl;穷举次数为 14次2.3 递推法与迭代法 递推递推法与法与迭代迭代法是两种风格类似的方法,它法是两种风格类似的方法,它们都是们都是基于分步递增基于分步递增方式进行求解,在许多方式进行求解,在许多其他更深入的算法设计方法中,都要结合这其他更深入的算法设计方法中,都要结合这两种方法两种方法 .2.3.1 递推法递推法(1/2)递推递推法是针对这样一类问题:问题的解决可以分为若干步骤,每个步骤都产生一个子解(部分结果),每个子解都是由前面若干子解生成。我们把这种由前面的子解得出后面的子解的规则称为递推关
12、系。例如例如,对于Fibonacci数列:1 1 2 3 5 8 13 21 34 设f(n)表示数列中第n项,则有:f(1)=1f(2)=1f(k)=f(k-1)+f(k-2)2.3.1 递推法递推法(2/2)递推法的运用有如下两个关键:n寻找递推关系:递推关系有解析和非解析两种。解析递推关系是指能用一般数学公式描述的关系,也称递推公式递推公式。非解析递推关系是指不能用一般的数学公式描述的关系,这类关系的描述,也许本身就是一个递推过程。递推关系必须有始基(最小子解)。n递推计算:递推计算的具体实现,可有非递归非递归和递递归归两种。非递归是自底向上计算,即按子解规模的先小后大的次序递推计算,递
13、归计算是指使用递归法计算,其形式上是自顶向下。关于递归法,我们将在后面集中讨论。递推法实现Fibonacci数列int Fibonacci(int n)int f1,f2,f3;int k;f1=1;f2=1;if(n=1)return 1;if(n=1)return 1;for(k=3;kprecision|x0-xprecision);/当最近两个近似解的差的绝对值小于给定精度时结束 return x;x2=aX2-1=a-1X=1+(a-1)/(1+x)2.4 递归2.4.1 递归与递归程序的概念 递归递归(Recursion)用来解决一类可归纳描述的问题,或说可分解为结构自相似的问题。
14、所谓结构自相似,是指构成问题的部分与问题本身在结构上相似。这类问题具有的特点是:整个问题的解决,可以分为两大部分:u是一些特殊(基础)情况是一些特殊(基础)情况,有直接的解法,即始始基基;u这部分与原问题这部分与原问题“相似相似”,可用类似(与整个问题的解法类似)的方法解决(即递归),但比原问题的规模小。2.4 递归(续1)递归问题在数学中很常见。例如,计算阶乘:F(0)=0 F(n)=n*F(n-1)当n0在该式中,f(n-1)的计算与原问题f(n)的计算“相似”,只是规模较小。(算术求和:S=n.)也有许多非算术计算问题可用递归方法解决。例如,设一维数组A的元素Ak1Ak2中存放整数,现要
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
限制150内