第九章 算法分析与设计 9.1 算法分析技术 9.2 算法设计技术 张乃孝 算法与数据结构——C语言描述

9.1 算法分析技术 评价一个算法的好坏，主要看执行算法时所需要占用的计算机空间的大小和计算过程需要花费的计算机CPU时间的多少。因此，算法的分析主要包含时间和空间两个方面。 9.1.1 空间代价分析 9.1.2 时间代价分析 张乃孝 算法与数据结构——C语言描述

9.1.1 空间代价分析 根据算法执行过程中对存储空间的使用方式，我们又把对算法空间代价分析分成两种情形：静态分析和动态分析。 9.1.1 空间代价分析 根据算法执行过程中对存储空间的使用方式，我们又把对算法空间代价分析分成两种情形：静态分析和动态分析。 1. 静态分析 一个算法静态使用的存储空间，是指在算法执行前，可以通过对程序静态的分析确定的使用空间，称为静态空间。 在静态空间分析中，值得注意的是数组（静态数组），它占用了大部分静态空间。 张乃孝 算法与数据结构——C语言描述

动态空间的确定主要由两种情况构成：（1）函数的递归；（2）调用动态分配（malloc）和回收（free）函数。 2. 动态分析 一个算法在执行过程中以动态方式使用的存储空间是指在算法执行过程中动态分配的存储空间，它们从程序的表面形式上不能完全确定，我们把在算法执行过程中才能确定的空间称为动态空间。 动态空间的确定主要由两种情况构成：（1）函数的递归；（2）调用动态分配（malloc）和回收（free）函数。 张乃孝 算法与数据结构——C语言描述

（1）函数的递归 例9.2　快速排序是一递归过程，调用该过程时，需分配的空间包括局部变量ｉ，ｊ和temp，形式参数１，ｒ和被排序的对象等。被排序对象用指针方式传递，调用时不必动态开辟新的空间，只须少量空间存放实参的地址等信息，所以递归调用时动态分配的空间与待排序记录的个数ｎ无关，为一常量。递归深度ｈ最大等于ｎ，这时动态空间代价为O(n)，若每次都选较短的部分先处理，则递归深度不会超过log2n，这时动态空间代价即为O(log2n)（参看算法7.9）。这里实际被排序对象的空间应算静态空间，显然是O(n)。 张乃孝 算法与数据结构——C语言描述

此时，动态空间代价为O(k)，k为使用malloc的次数。 （ⅱ）使用free函数 （2）调用动态分配和回收函数。 （ⅰ）没有使用free函数 此时，动态空间代价为O(k)，k为使用malloc的次数。 （ⅱ）使用free函数 不能简单的用malloc使用的次数减去free的使用次数作为动态空间的代价，应从malloc和free的具体执行情况来分析。 由书中（P284）算法进行动态空间代价分析，整个算法使用的动态空间代价为 张乃孝 算法与数据结构——C语言描述

9.1.2 时间代价分析 算法的执行时间绝大部分花在循环和递归上 1. 循环 循环语句的时间代价一般用以下三条原则分析： 9.1.2 时间代价分析 算法的执行时间绝大部分花在循环和递归上 1. 循环 循环语句的时间代价一般用以下三条原则分析： （１）对于一个循环，循环次数乘以每次执行简单语句的数目即为其时间代价。 （２）对于多个并列循环，可先计算每个循环的时间代价，然后按大Ｏ表示法的加法规则计算总代价。 （３）对于多层嵌套循环，一般可按大Ｏ表示法的乘法规则计算。但如果嵌套是有条件的，为精确计算其时间代价，要仔细累加循环中简单语句的实际执行数目，以确定其时间代价。 张乃孝 算法与数据结构——C语言描述

例9.6 求无回溯的匹配算法的时间代价（参看算法3.6）。 例9.6　求无回溯的匹配算法的时间代价（参看算法3.6）。 解　问题规模：模式串长度ｍ，目标串长度ｎ（ｎ＞ｍ）。 算法中有一个循环，在分析时应从算法执行效果具体分析。 因为ｉ＋１与ｊ＋１顺序执行，循环中ｊ只增不减，循环条件为ｉ＜ｍ且ｊ＜ｎ，所以ｊ＋１最多执行ｎ次，ｉ＋１也最多执行ｎ次。又因为next[i]＜ｉ，且循环过程中ｉ始终大于等于０，所以i:= next[i]执行ｎ次，总的时间代价为O(n)。 张乃孝 算法与数据结构——C语言描述

对于递归算法，一般可把时间代价表示为一个递归方程。解这种递归方程最常用的方法是进行递归扩展，通过层层递归，直到递归出口，然后再进行化简。 2．递归 对于递归算法，一般可把时间代价表示为一个递归方程。解这种递归方程最常用的方法是进行递归扩展，通过层层递归，直到递归出口，然后再进行化简。 下面给出一类递归方程的求解方法。设递归方程为： 张乃孝 算法与数据结构——C语言描述

递归扩展过程如下： 张乃孝 算法与数据结构——C语言描述

设ｎ＝ｂk，则 又设d(x)为“积性函数”即： ， 则有： 张乃孝 算法与数据结构——C语言描述

以下分三种情况讨论： （1）ａ＞d(b)，则 张乃孝 算法与数据结构——C语言描述

（2）ａ＜d(b)，则 张乃孝 算法与数据结构——C语言描述

（3）ａ＝d(b)，则 张乃孝 算法与数据结构——C语言描述

9.2 算法设计技术 9.2.1 分治法 9.2.2 贪心法 9.2.3 动态规划法 9.2.4 回溯法 9.2.5 分枝界限法 9.2 算法设计技术 9.2.1 分治法 9.2.2 贪心法 9.2.3 动态规划法 9.2.4 回溯法 9.2.5 分枝界限法 张乃孝 算法与数据结构——C语言描述

9.2.1 分治法(Divide and Conquer) 分治法是把一个规模为ｎ的问题分成两个或多个较小的与原问题类型相同的子问题，通过对子问题的求解，并把子问题的解合并起来从而构造出整个问题的解，即对问题分而治之。如果子问题的规模仍然相当大，仍不足以很容易地求得它的解，这时可以对此子问题重复地应用分治策略。(典型的应用分治策略的例子是二分检索法） 分治法处理问题的算法可以自然地写成一个递归的过程。一个用分治法编写的过程通常包括以下几部分：基值处理部分，（即把问题分到足够小后要进行的处理），分解问题的部分，递归调用部分和合并处理部分。 张乃孝 算法与数据结构——C语言描述

算法9.1给出了一般分治法程序的框架 算法9.1 分治法的算法框架 return_type d_and_c( objArray * p , int i , int j ) { int temp ; if ( simple (p,i,j) ) return solve (p,i,j) ; temp = divide (p,i,j) ; return(combine(d_and_c(p,i,temp-1),d_and_c(p,temp,j))); } 张乃孝 算法与数据结构——C语言描述

分治策略应用得较广泛。快速排序算法，归并排序算法、梵塔问题等都可以用分治策略求解。 分治策略把问题分成若干个子问题，分成的子问题的数目一般不大。如果每次分成的各子问题的规模相等或近乎相等的话，则分治策略的效率较高，否则效率就比较低。例如：直接插入排序可以看作是把原问题分解成两个子问题，一个是规模为１的问题，另一个是规模为n-1的问题，算法的时间代价是O(n２)级的。而归并排序把原问题分成了两个大小为n/2的问题，算法的时间代价是O(nlog2n)级的。 张乃孝 算法与数据结构——C语言描述

9.2.1 贪心法(greedy) 如果从某一给定的集合中选出一个子集，能够满足题目所给的要求，这个子集就是一个可行解。可行解不一定是唯一的。贪心法把构造可行解的工作分成许多阶段来完成。在各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。 但是，贪心法不是每次都能成功地产生出一个整体最优解。贪心法在每一阶段都保持着局部最优，而各阶段结果合起来，总的结果可能是不令人满意的，甚至有可能是坏的结果。 张乃孝 算法与数据结构——C语言描述

张乃孝 算法与数据结构——C语言描述

贪心法是一个很直接的算法设计技巧。用贪心策略求得问题的次优解是很快的。 使用贪心法，首先要根据问题的特点确定一种度量好坏的标准，然后按照这个标准对处理序列中的每个对象逐个进行考察，如果被考察的元素符合给定的标准，就把该元素加入到局部的最优解中。由于度量的标准可能有不同的观点，因此如何选择适当的标准往往是能否达到整体最优解的关键。 贪心法是一个很直接的算法设计技巧。用贪心策略求得问题的次优解是很快的。 贪心算法的各个阶段的局部最优的选择，一经确定就固定地作为解序列的一部分。ｎ步的选择就可得到一个较好的次优解（有可能是最优解，但是最优解一般是需经全排列所有测试才能得到的）。 贪心法常常帮助我们得到一个次优解。对某些问题，只有通过系统的、彻底的搜索才能得到最优解，从而使我们求得最优解的代价甚高，但是只要求得一个与最优解相差不多的次优解就可满足要求时，选用贪心法可以很快地得到较好的解 张乃孝 算法与数据结构——C语言描述

9.2.3 动态规划法（Dynamic Programming） 动态规划法与分治法的共同点是把一个大问题分解为若干较小的子问题，通过求解子问题而得到原问题的解。不同点是：分治法每次分解的子问题数目比较少，子问题之间界限清楚，处理的过程通常是自顶向下进行；动态规划法分解的子问题可能比较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果全部保存起来，通常是自底向上进行。 张乃孝 算法与数据结构——C语言描述

例9.10 求组合数 。 我们知道组合数有这样的一个递推式： 求 构造的表如右表所示。 4 1 3 10 6 2 5 0 n m 10 例9.10　求组合数 。 我们知道组合数有这样的一个递推式： 求 构造的表如右表所示。 4 1   3 10 6 2 5 0 n m 10 张乃孝 算法与数据结构——C语言描述

可以把前面构造的表改造一下：去掉ｎ＝0的那行，剩下的表中的左下角三个元素是不必要的（求 时不必求出它们），右上角的三个表目都空着没用，去掉这六个表目，把剩下的错开的表平移对齐，下标从0开始编址。得到如下表的矩阵。 10 4 1 6 3 2 2 1 0 2 1 张乃孝 算法与数据结构——C语言描述

由上看到，动态规划法是将一系列的子问题的解确定后填入表中，从而导出原问题的解。而贪心算法是进行了一系列的挑选，确定了一个较好的解。两者的相同点是它们都作出一系列的确定。它们的一个区别是，动态规划法先求子问题的解，然后通过求解子问题构造原问题的解；而贪心算法是直接地解原问题；另一区别是动态规划法一般产生多个子问题的解，从中选择最优解，而贪心法每阶段只作一个挑选。 动态规划法通过对若干局部最优解的比较，去掉了次优解。从而产生了更高一层次的局部最优解，保持了每个新产生的解都是该层次的局部最优解。相当于对较低层次的局部最优解进行贪心的选择而得到高一级的局部最优解，因而最终产生一个最高层次的局部最优解，它就是原问题所求的整体的最优解。 张乃孝 算法与数据结构——C语言描述

9.2.4 回溯法（backtracking） 应用回溯方法解问题时，这问题的解须能表示为一个元组，可以用树形结构来表示这些元组，从树根到树叶之间的路径就是一个元组（一个可能的解）。回溯方法通过系统的搜索来确定出问题的解，解问题就相当于用一种顺序周游这棵解答树。按照顺序进行试探，这是至关重要的，它保证了搜索的系统性和彻底性。穷举测试是对所有的叶子都一一访问，而回溯的方法是从树根开始，边试探边往下走，若在某一层次查明不符合题意，则不往下走，砍掉以下的树杈，跳到另一杈上继续试探着往下走。这样边走边砍，砍掉大量的树杈，从而省掉大量测试。一旦走到叶子，就找到了一组解。 由于用回溯方法解决问题时逐步产生出的解的序列是不能一经产生就固定不变的，而是一旦所产生的部分解序列不合题意就要回溯，修改刚产生出来的解，因此，回溯问题的算法中要用到栈。 张乃孝 算法与数据结构——C语言描述

算法9.4：一般回溯方法的程序结构 void 函数名 (void) { 准备初值； do { while (范围未超界并且工作未完成) { 准备初值； do { while (范围未超界并且工作未完成) { 分析条件；/* 保证不满足条件不往下去 */ if (成功) { 进堆栈； 由第一选择开始进入下一层次； /* 往下走 */ } else 本层更换选择； /* 横向走 */ if ( 工作未完成 ) { 弹出堆栈； 原来的上一层更换为下一选择； /* 回溯，上层横向走 */ while ( 全部工作未完成 ) ； 输出； 张乃孝 算法与数据结构——C语言描述

9.2.5 分枝界限法（branch and bound） 与回溯法相似，分枝界限法也是一种在表示问题解空间的树上进行系统搜索的方法。所不同的是，回溯法使用了深度优先策略，而分枝界限法一般采用广度优先策略或者采用最大收益（或最小损耗）策略，同时还利用最优解属性的的上下界来控制搜索的分枝。 本节主要结合0/1背包问题为例，重点介绍用最大收益的控制策略。 张乃孝 算法与数据结构——C语言描述

一个具体的0/1背包实例：已知n=4, m=15, w=(2,4,6,9), p=(10,10,12,18) 例9.14 一个具体的0/1背包实例：已知n=4, m=15, w=(2,4,6,9), p=(10,10,12,18) 求解x=(x1,x2,x3,x4)，（xi=0,1），使得 张乃孝 算法与数据结构——C语言描述

张乃孝 算法与数据结构——C语言描述

在使用分枝界限法搜索解的空间时，从根结点出发，每个结点最多处理一次，在生成当前结点的子结点时，把所有符合题目要求（wx≤m）并且在已知界值之内的结点放在一个活结点表中，然后从活结点表中取出一个结点作为当前结点。如此反复直到活结点表中只剩下一个叶结点为止。 在0/1背包的处理过程中，选择当前结点的策略可以按照u值的大小，把最大的取为当前结点，所以称为最大收益策略，这时活结点表可以组织成一个“堆”；与最大收益的分枝界限法相似，还有一种称为最小代价的分枝界限法。另外也可以按照先进先出的原则选择下一个当前结点，这时活结点表应该组织成一个队列。 在结束本节之前，我们还要对0/1背包问题补充一点。0/1背包问题最优解的方法很多，除去本节介绍的穷举法、回溯法（和用分枝界限改进的回溯法）、最大收益（最小代价）分枝界限法、FIFO分枝界限法等以外，也可以采用动态规划的方法。当0/1背包问题的n足够大时，如果只想得到一个较好的可行解，采用前面介绍的贪心法或者分治法有时也是十分有效的。 张乃孝 算法与数据结构——C语言描述

小 结 算法的分析主要包含时间和空间两个方面，空间代价分析分成两种情形：静态分析和动态分析。静态空间分析中，值得注意的是数组（静态数组），动态空间的确定主要考虑两种情况：函数的递归调用和空间的动态分配/回收。算法的执行时间绝大部分花在循环和递归上，循环的时间代价一般可以用加法规则和乘法规则估算；对于递归算法，一般可以解递归方程计算. 本章重点介绍了的五种常用的算法设计技术。 分治法通过把问题化为较小的问题来解决原问题，从而简化或减少了原问题的复杂度；贪心法通过分阶段地挑选最优解，较快地得到整体的较好解，在问题要求不太严格的情况下，可以用这个较优解替代需要穷举所有情况才能得到的最优解；动态规划法用填表的方法保存了计算的中间结果，从而避免了大量重复的计算；回溯法跳过大量无须测试的元组，很快地得到需要的解。而分枝界限法是在系统搜索问题解的空间时，加入上下界的条件检查以达到有效剪枝的目的。 张乃孝 算法与数据结构——C语言描述

分枝界限法、动态规划法和回溯法得到问题的最优解；贪心法既可能得到次优解，也可能得到最优解，依赖于具体问题的特点和贪心策略的选取。 这些方法的共同之处是运用技巧避免穷举测试。分治法和动态规划法都是将问题分成子问题来做的；贪心法、动态规划法以及回溯法都是从某一集合中选出子集，通过一系列的判定来得到解；贪心法、分枝界限法和回溯法都要进行逐项的测试比较逐步达到整个解；而动态规划法和回溯法都是逐步逼近最优解而最终得到满足条件的解。 分枝界限法、动态规划法和回溯法得到问题的最优解；贪心法既可能得到次优解，也可能得到最优解，依赖于具体问题的特点和贪心策略的选取。 对于某一问题来说，能用不同的设计技巧得到不同的算法，0/1背包问题就是典型的例子。一个算法中，也可以结合使用几种算法设计技巧。如快速排序算法是分治的技巧和回溯的技巧的结合，其中分治的技巧是主要的。 在设计程序时，要对题目进行全面的分析，根据题目的要求和所给条件，选用适当的数据结构和算法，并对算法的时间代价和空间代价做出适当的估计。 张乃孝 算法与数据结构——C语言描述