武汉理工大学-信息工程学院-数据结构-ppt-课件ch01-2-算法复杂度与常用算法

程序设计基本策略与方法学习目标：算法的基本概念算法的复杂度分析与度量穷举法递推法与迭代法递归法逐步求精法分治法2.1算法的基本概念2.1.1算法的概念算法：通俗而言，就是解决给定问题的方法。是规则的有穷序列，它为解决某一特定类型的问题规定了一个运算过程。具有下列特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步必须是确切定义的，对于每种情况，有待执行的每种动作必须严格地和清楚地规定。可行性：算法应该是可行的，它们都可由相应的基本计算装置所理解。输入：一个算法有零个或多个输入，它们是在算法所需的初始量或被加工的对象的表示。这些输入取自特写的对象集合。输出：一个算法有一个或多个输出，它们是与输入有特定关系的。算法的描述方法用自然语言，易产生歧义、繁琐、不被机器识别使用程序流程图、N-S图等算法描述工具。其特点是描述过程简洁、明了。用计算机语言描述，就是计算机程序。注意：1)计算机程序不一定就算一个算法：例如，操作系统，只要整个系统不遭破坏，它将永远不会停止。因此，操作系统不是一个算法。2)有些算法不能用计算机语言来描述：程序中的指令必须是机器可执行的，而算法中的指令则无此限制。什么是“好”的算法通常，从下列几个方面衡量算法的优劣：正确性。也称有效性，是指算法能满足具体问题的要求。亦即对任何合法的输入，算法都会得出正确的结果。可读性。指算法被理解的难易程度。可读性实质上强调的是：越简单的东西越美。健壮性（鲁棒性）。是指对非法输入的抵抗能力。它强调的是，如果输入非法数据，算法应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。高效(低时间复杂度与空间复杂度）。时间复杂度是指算法的运行的时间消耗，同一个问题，不同的算法可能有不同的时间复杂度。空间复杂度是指算法运行所需的存储空间的多少。robust2.1.2算法时间复杂度简单地讲，算法的时间复杂度是指算法的运行的时间消耗的大小，但这里的“运行”并不是指在具体机上的运行。一个算法在具体计算机上的运行速度，不仅取决于算法本身，而且与目标计算机（运行算法的计算机）的速度有关。如果算法是用非目标指令（如汇编语言、高级语言等）描述的，则运行速度还与描述语言的编译器所生成的目标代码的质量（或解释器本身的质量）有关。算法的时间复杂度指算法自身的抽象运行的时间消耗，与运行算法的目标计算机及描述算法的工具无关。只与算法本身以及问题的规模有关。时间复杂度相关因素算法的时间复杂度与下列因素有关：问题性质：有的问题比较复杂，而有的比较简单；问题规模：同一问题，同一算法，其处理的对象的规模不同，则耗时也不同；算法性质：同一问题，不同的解决方法，效率也不同。一个算法的时间复杂度通常用函数描述（时间复杂度函数）。时间复杂度函数通常可以描述为问题规模的函数。[例]算法不同时间复杂度不同32axbxcxdsaxxxbxxcxd计算三次多项式直接计算方法运算量（时间）：6次乘法，3次加法一种新方法;;;;sassxbssxcssxd运算量（时间）：3次乘法，3次加法.时间复杂度的渐进表示复杂度的渐进表示：复杂度的精确表示很困难，许多算法的时间复杂度函数不能以解析形式给出。所以通常用某些简单函数近似表示。常用的上界函数有:log(n),nm,an,n!,......下面给出几种常见的函数的比较关系：即当n充分大时，下列关系成立：O(a)O(logn)O(n)O(n.logn)O(n2)...O(nm)O(an)O(n!)O(nn)上面，n为自变量，a和m为常数算法的时间复杂度的分类多项式时间复杂度算法：渐近函数为多项式，或变化率不超过多项式。指数时间复杂度算法：渐近函数变化率超过多项式，这类算法也称NP（nondeterministicpolynomial）-困难的算法。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题.2.1.3算法时间复杂度的度量语句频度（FrequencyCount）是指语句被重复执行的次数。即对某语句，若在算法的一次运行中它被执行n次，则它的语句频度为n。我们用算法中的各语句的语句频度之和表示算法的时间复杂度[例1.8](1/2)考虑下列子程序，它的功能是求出数组a中各数的大小次序号，存入数组b中的对应位置。例如，若a[]={4,2,3,9,6,8,7},则程序结束后，数组b内容为b[]={3,1,2,7,4,6,5},表示4，2，3，9，6，8，7的大小次序分别为3，1，2，7，4，6，5.voidOrderNumbers(int*a,intn,int*b){inti,j;for(i=0;in;i++)b[i]=1;…………………(1)：nfor(i=0;in-1;i++)…………………………(2)：n-1for(j=i+1;jn;j++)……………………….(3)：if(a[i]a[j])……………………………….(4)：b[j]++;…………………………………..(5):最多为elseb[i]++;return;}10)1(niin10)1(niin10)1(niin[例1.8](2/2)总的语句频度最大为：n+(n-1)+3=2n-1+3(n-1)n/2=3n2/2+7n/2–1=O(n2)10)1(niin2.1.4空间复杂度空间复杂度（Spacecomplexity）是指程序运行从开始到结束所需的存储量程序运行所需的存储空间包括以下两部分：⑴固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。⑵可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。2.2穷举法穷举法(枚举法/试探法)的基本思想是：分别列举出各种可能解，测试（试探）其是否满足条件（是否是欲求的解），若是，则输出之。特点是算法简单，但是运算量大。当问题的规模变大，执行的的速度变慢。[例1]解不定方程。不定方程（组）是指独立方程个数少于变量个数而导致方程有多解。如，2x+3y=20是一个不定方程（设x,y为正整数）。解这个方程，就是求出所有的解。不定方程一般都有限定条件，我们这里考虑正整数解的情况。解这个方程，一个简单的做法是，让x和y分别遍取0到20内的正整数，并代入方程计算，若值为20，则表示找到一组解。具体的程序片断如下。for(i=0;i=20;i++)for(j=0;j=20;j++)if(2*i+3*j==20)cout\ni,j;穷举法例2百钱买百鸡：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？根据题意列方程5x+3y+z/3=100x+y+z=100(x,y,z=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''y''zendl;｝穷举次数为101＋100＋…+1=5151次穷举法的优化方程可以转化为：7x+4y=100x+y+z=100(x,y,z=0;z被3整除)程序为：for(x=0;x=14;x++){y=100-7*x;if(y%4)continue;elsey/=4;z=100-x-y;if(z%3)continue;coutx''y''zendl;�}穷举次数为14次2.3递推法与迭代法递推法与迭代法是两种风格类似的方法，它们都是基于分步递增方式进行求解，在许多其他更深入的算法设计方法中，都要结合这两种方法.2.3.1递推法(1/2)递推法是针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成。我们把这种由前面的子解得出后面的子解的规则称为递推关系。例如，对于Fibonacci数列：112358132134…设f(n)表示数列中第n项，则有：f(1)=1f(2)=1f(k)=f(k-1)+f(k-2)2.3.1递推法(2/2)递推法的运用有如下两个关键：寻找递推关系：递推关系有解析和非解析两种。解析递推关系是指能用一般数学公式描述的关系，也称递推公式。非解析递推关系是指不能用一般的数学公式描述的关系，这类关系的描述，也许本身就是一个递推过程。递推关系必须有始基（最小子解）。递推计算：递推计算的具体实现，可有非递归和递归两种。非递归是自底向上计算，即按子解规模的先小后大的次序递推计算，递归计算是指使用递归法计算，其形式上是自顶向下。关于递归法，我们将在后面集中讨论。递推法实现Fibonacci数列intFibonacci(intn){intf1,f2,f3;intk;f1=1;f2=1;if(n==1)return1;if(n==2)return1;for(k=3;k=n;k++){f3=f1+f2;f1=f2;f2=f3;}returnf3;}非递归2.3.2迭代法迭代法和递推法类似，也是递增求解，但不同的是，递推法中，每步得到的解都是相对于对应问题规模的完整解。但对迭代法，中间步骤得到的解一般只是“近似解”，并不代表子问题的解（常常没有明确的子问题）。当误差达到可接受的范围时，则认为“近似解”就是需要的结果。例：求a的平方根(迭代法)floatSqrt(floata){floatprecision=0.0001;//定义解的精度floatx,x0;x=1;do{x0=x;x=1+(a-1)/(x+1);}while(x-x0precision||x0-xprecision);//当最近两个近似解的差的绝对值小于给定精度时结束returnx;}x2=aX2-1=a-1X=1+(a-1)/(1+x)2.4递归2.4.1递归与递归程序的概念递归(Recursion)用来解决一类可归纳描述的问题，或说可分解为结构自相似的问题。所谓结构自相似，是指构成问题的部分与问题本身在结构上相似。这类问题具有的特点是：整个问题的解决，可以分为两大部分：是一些特殊（基础）情况，有直接的解法，即始基；这部分与原问题“相似”，可用类似（与整个问题的解法类似）的方法解决（即递归），但比原问题的规模小。2.4递归（续1）递归问题在数学中很常见。例如，计算阶乘：F(0)=1F(n)=n*F(n-1)当n0在该式中，f(n-1)的计算与原问题f(n)的计算“相似”，只是规模较小。(算术求和：S=∑n.)也有许多非算术计算问题可用递归方法解决。例如，设一维数组A的元素A[k1]~A[k2]中存放整数，现要求出它们中最大者，递归求法为：a)若k1=k2，则A[k1]即为所求；b)若k1k2，则先按类似的方法，求出A[k1+1]~A[k2]中最大者，设其为m，然后，比较A[k1]和m，二者中最大者即为所求。2.4递归（续2）例如，关于阶乘的计算，可通过下列的递归程序：longFact(intn){if(n=0)return1;//第一部份，始基elsereturnn*Fact(n-1);//第二部份，用实参n-1递归调用}再如，在一维数组中求最大值的程序为：intGetMax(inta[],intk1,intk2){intm;if(k1==k2)returna[k1];//第一部份，始基m=GetMax(a,k1+1,k2);//第二部份，与原问题类似，规模更小。if(a[k1]m)returna[k1];elsereturnm;}2.4.2递归程序设计要点（续3）划分问题、寻找递归：许多问题，并没有明显的递归解法，这就需要寻找递归方案