数据结构第11章.pptVIP

第11章 算法设计与分析 一、算法 算法是解决问题的策略、规则和方法。数据结构操作的实现方法就是一类典型的算法问题。 算法具有5个特性： 1、有穷性 2、确定性 3、可行性 4、输入 5、输出 评价算法的基本标准 1、正确性 2、可读性 3、健壮性 4、时间复杂度与空间复杂度 时间复杂度 算法的时间复杂度是指算法的运行时间。 影响运行时间的主要因素有： 目标计算机的速度 编译器所生成的目标代码的质量 程序处理的数据量 算法的设计 注意：为了排除与算法设计无关的因素，在这里所说的“运行”是指抽象的运行，即不涉及具体的计算机设备和语言工具。 时间复杂度函数 通常时间复杂度用以数据规模为自变量的函数表示，即T(n)。 常见的时间复杂度有： O(1)O(logn)O(n)O(nlogn)O(n2)....; 空间复杂度 影响算法空间复杂度的因素有： 原始数据占据的空间 算法运行时，开辟的辅助空间 空间复杂度只考虑辅助空间量，因此，空间复杂度用以辅助空间量作为自变量的函数描述。 举例：最大连续子序列之和问题 给出n个整数A1,A2,...,An（可以为负值），试找出若干个连续整数之和为最大值的子序列。如果所有整数均为负值，则最大值为0。 {-1，11，-4，13，-5，2}的最大值为20 {1，-3，4，-2，-1，6}的最大值为7 算法1：穷举法 int maxSubSequenceSum(int [] a) { maxSum=0; for (i=0;ia.length;i++) //n次 for (j=i;ja.length;j++) { //最坏情况n次 thisSum=0; for (k=i;k=j;k++) thisSum+=a[k]; //最坏情况n次 if (thisSummaxSum){ maxSum=thisSum; seqStart=i; seqEnd=j; } } return maxSum; } 算法2：改进 int maxSubSequenceSum(int [] a) { maxSum=0; for (i=0;ia.length;i++) { //n次 thisSum=0; for (j=i;ja.length;j++) { //最坏情况n次 thisSum+=a[j]; if (thisSummaxSum){ maxSum=thisSum; seqStart=i; seqEnd=j; } } } return maxSum; } 算法3：线性 int maxSubSequenceSum(int [] a) { maxSum=0; thisSum=0; for (i=0,j=0;ja.length;j++) { thisSum+=a[j]; if (thisSummaxSum){ maxSum=thisSum; seqStart=i; seqEnd=j; } else if (thisSum0){ i=j+1; thisSum=0; } } return maxSum; } 二、递推法与迭代法 递推法与迭代法都是基于分步递增方式进行求解的。 递推法的基本方法： 将问题的解决分为若干个步骤，每个步骤都产生一个子解，每个子解都是由前面若干个子解生成，它们均与问题规模相关，且是相关问题规模的完整解。 典型实例：斐波那契数列 递推法的关键： 寻找递推关系 确定递推计算 递推法的实现： 递归 非递归 迭代法 迭代法与递推法类似，也是递增求解。但递推法每步得到的解都是对应问题规模的完整解，而迭代法中间步骤得到的解一般只是“近似解”，而不代表子问题的解。 三、递归法与