数据结构和算法C2.ppt

第二章程序设计基本策略与方法 递归、逐步求精、分治是基本的算法（程序）设计策略与方法。许多复杂问题，使用它们都可迎刃而解。这几种策略与方法在后面要经常使用，这里先介绍它们的基本思想，进一步的例子将在后面的章节中见到。做为基础，我们先介绍算法的概念  2.1 算法的基本概念 2.1.1算法的概念 一、算法的概念 一个算法是规则的有穷序列，它为解决某一特定类型的问题规定了一个运算过程，并且具有下列特性： 有穷性：一个算法必须在执行有穷步之后结束。 确定性：算法的每一步必须是确切定义的，对于每种情况，有待执行的每种动作必须严格地和清楚地规定。 可行性：算法应该是可行的，这意味着算法中所有有待实现的运算都是基本的，即它们都可由相应的基本计算装置所理解，并可通过有穷次运算即可完成。 输入：一个算法有零个或多个输入，它们是在算法所需的初始量或被加工的对象的表示。这些输入取自特写的对象集合。 输出：一个算法有一个或多个输出，它们是与输入有特定关系的量 二 、什么是“好”的算法 通常，从下列几个方面衡量算法的优劣： 正确性。也称有效性，是指算法能满足具体问题的要求。亦即对任何合法的输入，算法都会得出正确的结果。可读性。指算法被理解的难易程度。人们现在常把算法的可读性放在比较重要的位置，主要是因为晦涩难懂的算法不易交流、推广使用，也难以修改、扩展与调试，而且可能隐藏较多的错误。可读性实质上强调的是：越简单的东西越美。 健壮性（鲁棒性）。是指对非法输入的抵抗能力。它强调的是，如果输入非法数据，算法应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。 时间复杂度与空间复杂度。时间复杂度是指算法的运行的时间消耗，同一个问题，不同的算法可能有不同的时间复杂度。 2.1.2 算法时间复杂度与空间复杂度 简单地讲，算法的时间复杂度是指算法的运行的时间消耗的大小，但这里的“运行”，是指抽象的运行，并不是指在具体机上的运行。一个算法在具体计算机上的运行速度，不仅取决于算法本身，而且与目标计算机（运行算法的计算机）的速度有关，如果算法是用非目标指令（如汇编语言、高级语言等）描述的，则运行速度还与描述语言的编译器所生成的目标代码的质量（或解释器本身的质量）有关。 算法的时间复杂度指算法自身的抽象运行的时间消耗，与运行算法的目标计算机及描述算法的工具无关 、相关因素 算法的时间复杂度与下列因素有关： 问题性质：有的问题比较复杂，而有的比较简单； 问题规模：同一问题，同一算法，其处理的对象的规模不同，则耗时也不同； 算法性质：同一问题，不同的解决方法，效率也不同。 一个算法的时间复杂度通常用函数描述（时间复杂度函数）。时间复杂度函数通常可以描述为输入规模的函数。输入规模可以是输入量或输出量，或两者之和，也可以是某种测度（如数组维数、图的边数等），它可用一个或多个量代表 下面举一个简单的例子。 [例] 考虑计算三次多项式 ax3 + bx2 + cx + d 一种直接的计算方法是： s=a*x*x*x + b*x*x + c*x + d; 该算法共执行6次乘法，3次加法。 考察另一种解法： s=a; s=s*x+b; s=s*x+c; s=s*x+d; 该算法共进行3次乘法，3次加法。显然该算法的计算量少于前一种方法，尽管其看上去较复杂。第二种算法基于的原理是逐步提取共因子： a*x*x*x + b*x*x + c*x + d = (ax+b)x2 + cx + d =((ax+b)x + c)x + d 二、复杂度的渐近表示 常用的上界函数有 log(n), nm, an, n! 下面给出几种常见的函数的比较关系：即当n充分大时，下列关系成立： O(a) O(log n) O(n) O(n.log n) O(n2) ... O(nm) O(an) O(n!) O(nn) 这里，n为自变量，a和m为常数 定理 2?1 若A(n) = amnm + … +a1n + a0 是关于n的一个m次多项式，则 A(n) = O(nm) 三、算法的时间复杂度的分类 多项式时间复杂度算法：渐近函数为多项式，或变化率不超过多项式。 指数时间复杂度算法：渐近函数变化率超过多项式，这类算法也称NP-困难的算法。 2.1.3算法时间复杂度的度量 语句频度（Frequency Count）是指语句被重复执行的次数。即对某语句，若在算法的一次运行中它被执行n次，则它的语句频度为n。语句频度也可称为程序步数 我们用算法中的各语句的语句频度之和表示算法的时间复杂度 [例 1.8] 考虑下列子程序，它的功能是求出数组