《第二讲 算法和算法分析》由会员分享，可在线阅读，更多相关《第二讲 算法和算法分析（4页珍藏版）》请在金锄头文库上搜索。
1、第二讲算法和算法分析1. 了解算法、算法正确性、复杂性2. 了解算法的时间与空间复杂性级别3. 掌握常见算法代价的求解教学重点：1. 算法的时间与空间复杂性级别2. 常见算法代价的求解教学难点：估算算法的时间夏杂度的方法授课内容1.2算法和算法描述算法与数据结构的关系紧密，在算法设计时先要确定相应的数据结构，而在讨论某一 数据结构时也必然会涉及相应的算法。下面就从算法特性、算法描述、算法性能分析与度量 等三个方面对算法进行介绍。1.2.1什么是算法算法(Algorithm)是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一 条指令表示一个或多个操作。一个算法应该具有下列特性：有穷性。一
2、个算法必须在有穷步之后结束，即必须在有限时间内完成。确定性。算法的每一步必须有确切的定义，无二义性。算法的执行对应着的相同的输 入仅有唯一的一条路经。可行性。算法中的每一步都可以通过已经实现的基木运算的有限次执行得以实现。输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。输出。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系 统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等 待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算
3、 法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 一个算法若用程序设计语言来描述，则它就是一个程序。算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结 构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各神算法的执行 来体现。要设计一个好的算法通常要考虑以下的要求。正确。算法的执行结果应当满足预先规定的功能和性能要求。可读。一个算法应当思路清晰、层次分明、简单明了、易读易憧。健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。高效。有效使用存储空间和有较高的时间效率。1.2.2算法描述算法可以使用各神不同的方法
4、来描述。最简单的方法是使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法 的阅读。缺点是不够严谨。可以使用程序流程图、NS图等算法描述工具。其特点是描述过程简洁、明了。用以上两种方法描述的算法不能够直接在计算机上执行，若要将它转换成可执行的程序 还有一个编程的问题。可以直接使用某种程序设计语言来描述算法，不过直接使用程序设计语言并不容易，而 且不太直观，常常需要借助于注释才能使人看明白。为了解决理解与执行这两者之间的矛盾，人们常常使用一 种称为伪码语言的描述方法来 进行算法描述。伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言 中一些严格的语法规则与描述细节，因此
5、它比程序设计语言更容易描述和被人理解，而比日 然语言更接近程序设计语言。它虽然不能直接执行但很容易被转换成高级语言。木书用类C语言描述算法，类C语言实际上是对C语言的一种简化精选了 C的一个了 集，扩充修改，增强了语言的描述功能。 预定义常量和类型 数据结构的表示：存储结构用类型（typedef）定义来描述。数据元素类型约定为ElemType. 基木操作的算法用函数描述：函数类型函数名（函数参数表）算法说明语句序列 函数名增加了引用调用的参数传逆方式。 赋值语句、选择语句、循环语旬、结束语旬、输入输出语旬、注释语句 基木函数 逻辑运算约定1.3算法分析技术初步我们可以从一个算法的时间复杂度与空
6、间复杂度来评价算法的优劣。当我们将一个算法转换成程序并在计算机上执行时,其运行所需要的时间取决于下列因 素：硬件的速度。例如使用486机还是使用586机。书写程序的语言。实现语言的级别越高，其执行效率就越低。编译程序所生成bl标代码的质量。对于代码优化较好的编译程序其所生成的程序质量 较局。问题的规模。例如，求100以内的素数与求1000以内的素数其执行时间必然是不同 的。显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用 执行算法的绝对时间来衡量算法的效率是不含适的。为此，可以将上述各种与计算机相关的 软、硬件因素都确定下来,这样一个特定算法的运行工作景的大小就只依
7、赖于问题的规模(通 常用正整数n表示)，或者说它是问题规模的函数。1.3.1 时间复杂度一个程序的时间复杂度(Time comp I ex i ty )是指程序运行从开始到结束所需要的时间。一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于 比较同一问题的不同的算法，通常的做法是：从算法中选取一神对于所研究的问题来说是基 本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原 操作重复执行的次数是规模n的某个函数T(n)0许多时候要精确地计算T(n)是困难的，我们引入渐进时间夏杂度在数量上估计一个算法 的执行时间，也能够达到分析算法的目的。定
8、义(大。记号)：如果存在两个正常数c和n,使得对所有的n, nn0,有：f(n) W cg(n)则有:f(n) = 0 (g(n)例如，一个程序的实际执行时间为T(n) = 2.7n3+3.8n2+5.3o则T(n)= 0(/)。使用大。记号表示的算法的时间复杂度，称为算法的渐进时间复杂度(Asymptotic Comp I ex i ty )0通常用。(l)表示常数计算时间。常见的渐进时间复杂度有：0(1)0 (log2n) 0(n)0 (nlog2n) 0 (n2) 0 (n3) O (2n) 【例1】：求两个n阶方阵的乘积C=AXB,其算法如下：#define n 100void Mat
9、rixMultiply(int Ann,int Bnn,int CnnJ)int i,j,kfor (i= 1 ;iv=n;+i)n+1for (j=l；j=:n;+j)n*(n+l)CiJUl=O；n2for (k=l ;kv=n,k+)n2(n+l)Cij=Cij+aik*bk|J; n3)T(n)=2n3+3n2+2n+1 limT(n)/ n3=2T(n)=0(n3)【例2】(a) +x;s=O;(b) for (i=l;iv=n;+i) +x;s+=x;(c) for(j=l;jv=n;+j)for (k=l;kv=n;k+)+x;s+=x;含基本操作“x增1”的语句的频度分别为l,
10、n和n2时间复杂度是0,0(n)和O(n2)o时间复杂度有时与输入有关。1.3.2空间复杂度一个程序的空间复杂度(Space complexity)是指程序运行从开始到结束所需的存储量。程序的一次运行是针对所求解的问题的某一特定实例而言的。例如，求解排序问题的排 序算法的每次执行是对一组特定个数的元素进行排序。对该组元素的排序是排序问题的一个 实例。元素个数可视为该实例的特征。程序运行所需的存储空间包括以下两部分：(1)固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征 无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。 例如10()个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同 的。总结1、算法的特性；2、算法设计要求：正确性、可读性、健壮性、效率与低存储量需求;3、渐近时间复杂度；4、空间复杂度；
