9.1算法分析技术9.1.1空间代价分析9.1.1空间代价分析9.1.2时间代价分析9.1.2时间代价分析2。递归a<d(b)：9.2算法设计技术9.2.1分治法一个用分治法编写的过程通常包括以下几部分：基值处理部分，（即把问题分到足够小后要进行的处理），分解问题的部分，递归调用部分和合并处理部分。由于分治策略是把问题分成较小的与原问题类型相同的子问题，对子问题的处理过程与对原问题的处理过程是相同的。所以，分治法处理问题的算法可以自然地写成一个递归的过程。例：二分法查找、汉诺塔问题、八皇后问题、快速排序法、归并排序法等。9.2.2贪心法贪心法常常帮助我们得到一个次优解。对某些问题，只有通过系统的、彻底的搜索才能得到最优解，从而使我们求得最优解的代价甚高，但是只要求得一个与最优解相差不多的次优解就可满足要求时，选用贪心法可以很快地得到较好的解。例9.9背包问题：给定ｎ个物体和一个背包，已知物体ｉ的重量为ｗi＞０，背包能容纳物体的重量为Ｍ。要求确定一组分数ｘi（０≤ｘi≤１），把物体ｉ的ｘi部分放入背包，使得最大（ｐi＞０也是已知的，是物体ｉ的总价格），即将尽量多的价值装入背包。9.2.3动态规划法例9.11给定一个多边形和各顶点的坐标。要求产生一组互不相交的弦（不相邻顶点间的连线），将此多边形划分成若干三角形，使得弦的总长最小。图9.2给出了一个七边形。用动态规划法来解此问题，可作如下分析：如果找到一种划分，因为要求弦互不相交，所以任何一边，必定与某一顶点构成一个三角形，例如边(Ｖ０Ｖ６)必定属于某ΔＶ０Ｖ６Ｖｋ，这里的ｋ是１，２，３，４，５中的某个值。ΔＶ０Ｖ６Ｖｋ将此七边形分割成两个部分：一部分是多边形Ｖ０Ｖ１…Ｖｋ；另一部分是多边形ＶｋＶｋ＋１…Ｖ６。一般地，用Ｓｉｊ表示从Ｖｉ开始连续ｊ个顶点所构成的多边形，Ｃｉｊ表示ｊ边形Ｓｉｊ的一种划分所产生的弦的总长，Ｄ（Ｖｉ，Ｖｊ）表示Ｖｉ到Ｖｊ之间的弦长，则有以下等式：本书所见过的运用动态规划法的算法有：所有结点间的最短路径算法（算法8.5）及最佳二叉排序树的构造算法（参看算法6.8）。9.2.4回溯算法八皇后问题迷宫问题深度优先周游树或图例9.12四色问题：给定图9.5，其中０１，０２，…，０７标明七个区域，要求用不多于四种颜色对这七个区域进行着色，使得有公共界的区域不同色应用回溯方法解问题时，这问题的解须能表示为一个元组。例骑士周游问题。给定一个ｎ×ｎ的方阵，共有ｎ２个区域，有一个国际象棋的马置于一个区域上，要求找到一条路径，使马按国际象棋的允许走法，从开始区域出发，不重复地把ｎ２个区域都恰好经过一次。一般回溯方法的程序结构。void函数名(void){准备初值；do{while(范围未超界并且工作未完成){分析条件；/*保证不满足条件不往下去*/if(成功){进堆栈；由第一选择开始进入下一层次}else本层更换选择；/*横向走*/}if(工作未完成){弹出堆栈；原来的上一层更换为下一选择；/*回溯，上层横向走*/}}while(全部工作完成)；输出；}小结有时对同一个问题，可以使用不同的算法来实现：例0/1背包问题：给定ｎ个物体和一个背包，已知物体ｉ的重量为ｗi＞０，背包能容纳物体的重量为Ｍ。要求确定一组分数ｘi（限制ｘi取0和１两个值），把物体ｉ的ｘi部分放入背包，使得最大（ｐi＞０也是已知的，是物体ｉ的总价格），即将尽量多的价值装入背包。（1）用分治法来做。数组Ｗ[1．．n]按Ｐ/Ｗ值的递增的顺序存放物体的重量，Ｐ[1．．n]放对应物体的价格，x[1．．n]是解向量。给定背包能放的总重量，求解时可以把它分为两种情况：一种是如果Ｗ[n]＞Ｍ，则化为求解对前n-1个物体的0/1背包问题，即x[n]取0；另一种是如果Ｗ[n]≤Ｍ，则x[n]取1，问题化为对能容纳重量为Ｍ-Ｗ[n]的背包和前n-1个物体的背包问题。所以，可把原问题化为子问题，用递归的方式解。（2）用动态规划法来解。也分成上述的两种情况。设fn(Ｍ)为所求，则它可由如下的递推式得到：将ｎ改成ｉ，ｉ从０变到ｎ，上式变为：在Ｍ＜０时，取fi(Ｍ)＝－∞。从ｆ0(ｘ)＝0开始，顺序地将ｆ1，ｆ2，…，ｆn填表，得到它的最优解fn。这时对Ｗ的存放顺序没有要求。（3）用回溯的方法解这个问题。通过构造解答树的方式来实现。一个算法中，也可以结合使用几种算法设计技巧。如快速排序算法是分治的技巧和回溯的技巧的结合，其中分治的技巧是主要的。