第十章 算法分析与设计.pptVIP

第十章 算法分析与设计 读者在学习以前各章的基础上，系统地阅读本章，可对算法的设计和分析技术有一个鸟瞰，以便于将本书所学到的算法归类整理，达到开阔思路，提高观点，增强兴趣的目的。 目录 10.1 算法分析技术 10.1.1 空间代价分析 10.1.2 时间代价分析 10.2 算法设计技术 10.2.1 分治法 10.2.2 贪心法 10.2.3 动态规划法 10.2.4 回溯法 10.2.5 分枝界限法与0/1背包问题* 10.1 算法分析技术 评价一个算法的代价，主要看执行算法时所需要占用的计算机空间的大小和计算过程需要花费的计算机CPU时间的多少。 算法的分析主要包含时间和空间两个方面。 10.1.1 空间代价分析 根据算法执行过程中对存储空间的使用方式，可以把对算法空间代价分析分成两种：静态分析和动态分析。 静态分析 一个算法静态使用的存储空间，称为静态空间。 静态分析的方法比较容易，只要求出算法中使用的所有变量的空间，再折合成多少空间存储单位即可。 例10.1　直接插入排序的空间代价分析（参看算法8.1） 被排序的记录的个数ｎ决定了问题的规模。 被排序的对象在调用函数中申请，并用一个指针变量pvector传递给被调函数，空间大小显然是O(n)； 在排序程序中，算法以静态方式定义了两个整型变量i和j、一个存储插入元素的临时变量temp，所以在算法中分配的空间为一个 常量，记为O(1)（对于常量c而言，O(c)与O(1)为相同复杂度）。 动态分析 一个算法在执行过程中，必须以动态方式分配的存储空间是指在算法执行过程中才能分配的空间称为动态空间。 动态空间的确定主要由两种情况构成： （1）函数的递归； （2）执行动态分配函数。 函数的递归调用 对于递归函数而言，由于每次调用需要分配不同的运行空间，所以递归函数的空间代价，不能简单地采用静态分析方法。 假设静态分析一个递归函数的空间代价为一个常量c，如果递归深度为ｈ（h的大小依赖于程序的动态执行），动态空间代价应该为C*h。  例10.2 快速排序（参看算法8.8） 对函数静态分析的空间与待排序记录的个数ｎ无关，为一常量。递归深度ｈ最大等于ｎ，这时动态空间代价为O(n)；若每次都选较短的部分先处理，则递归深度不会超过log2n，这时动态空间代价即为O(log2n)。 执行动态分配函数 一个函数（或过程）如果使用了malloc和free函数，malloc和free所开辟、释放的空间只能在算法执行过程中加以确定，这些空间属于动态空间。 下面的讨论中，假设每次分配的空间与问题规模无关，只是一个常数C。  没有使用free函数 动态空间代价为O(k)，k为使用malloc的次数（包括在循环和递归调用中动态执行的次数）。 使用free函数 设free使用次数为j。 令：ｃ0＝１， pi（i=1..j）为第i-1次使用free和ｉ次使用free之间 执行malloc的次数。 用公式ｃi=ｃi-1+ p i-1 可以计算出在第i-1次使用free和第i次使用free（i=1..j）之间使用的最大动态空间数。 再定义j’如下： 于是整个算法使用的动态空间代价为： 例10.3 一个算法执行过程中malloc和free顺序为（ｎ代表malloc，ｄ代表free）。 ｎｎｎｄｄｎｄｄｎｎｎｄｎｄｄ, j＝j’＝７ Ｃ0 =１， Ｃ1＝３， Ｃ2＝２， Ｃ3＝２， Ｃ4＝１， Ｃ5＝３， Ｃ6＝３， Ｃ7＝２。 10.1.2 时间代价分析 算法的执行时间绝大部分花在循环和递归上。  循环 循环语句的时间代价一般用以下三条原则分析： （１）　对于一个循环，循环次数乘以每次执行简单语句的数目即为其时间代价。 （２）　对于多个并列循环，可先计算每个循环的时间代价，然后按大Ｏ表示法的加法规则计算总代价。 （３）? 对于多层嵌套循环，一般可按大Ｏ表示法的乘法规则计算。但如果嵌套是有条件的，为精确计算其时间代价，要仔细累加循环中简单语句的实际执行数目，以确定其时间代价。 例10.5　求带权图中每一对结点之间的最短路径的算法的时间代价（参看算法9.7）。解 问题规模：带权图顶点数目为ｎ。算法中共有五个循环，前两个循环与后三个是并列