第九章算法分析与设计

《第九章算法分析与设计》由会员分享，可在线阅读，更多相关《第九章算法分析与设计（30页珍藏版）》请在金锄头文库上搜索。

1、第九章 算法分析与设计算法与数据结构的关系 不了解施加于数据上的算法就无法决定 如何构造数据； 反之算法的结构和选择又常常在很大程 度上依赖于作为基础的数据结构。 算法数据结构程序9.1算法分析技术 9.1.1空间代价分析静态分析 动态分析 9.1.2时间代价分析循环 递归9.1.1空间代价分析1。静态分析 求出算法中使用的所有变量的存储空间，再 折合成多少空间单位即可。 void insertSort(SortObject * pvector) inti, j; RecordNodetemp; for( i = 1; i n; i+ ) temp = pvector-recordi; j =

2、 i-1; while(temp.keyrecordj.key)j-; if(j!=(i-1) pvector-recordj+1 = temp; 9.1.1空间代价分析2。动态分析动态空间的确定主要由两种情况构成： （1）函数的递归； （2）调用动态分配（malloc）和回收（free）函数（1）函数的递归； 递归深度为，动态空间代价为C*h （2）调用动态分配（malloc）和回收（free）函 数 主要考虑分配内存大小与规模无关的情况 。这时空间代价由分配和回收的次数决定。9.1.2时间代价分析算法的执行时间绝大部分花在循环和递归上。 1。循环循环语句的时间代价一般用以下三条原则分析：

3、对于一个循环，循环次数乘以每次执行简单语句的数 目即为其时间代价。 对于多个并列循环，可先计算每个循环的时间代价， 然后按大表示法的加法规则计算总代价。 对于多层嵌套循环，一般可按大表示法的乘法规则 计算。但如果嵌套是有条件的，为精确计算其时间代价 ，要仔细累加循环中简单语句的实际执行数目，以确定 其时间代价。9.1.2时间代价分析循环分析示例1： int Index_KMP(SeqString t, SeqString p, int pos) inti, j, *next; next = (int *)malloc(sizeof(int)*(p.n+1); GetNext(p, next);

4、 j = pos; i = 0; while(i = p.n) return (j p.n+1);/* Found */ else return -1; /* end of Index_KMP() */2。递归 对于递归算法，一般可把时间代价表示 为一个递归方程。ad(b)：ad(b)：ad(b)：例 求快速排序法的时间代价。 解 此算法的递归方程可表示为： T(n)T(n/2)n，这里，d(x)是 积性函数。因为d(b)，所以9.2算法设计技术 最基本的算法设计技术： 分治法 贪心法 动态规划法 回溯法9.2.1分治法分治策略是把一个规模为的问题分成两 个或多个较小的与原问题类型相同的子问

5、题，通过对子问题的求解，并把子问题的 解合并起来从而构造出整个问题的解，即 对问题分而治之。如果子问题的规模仍然 相当大，仍不足以很容易地求得它的解， 这时可以对此子问题重复地应用分治策略 。一个用分治法编写的过程通常包括以下几部分：基值处理 部分，（即把问题分到足够小后要进行的处理），分解问 题的部分，递归调用部分和合并处理部分。由于分治策略是把问题分成较小的与原问题类型相同的子 问题，对子问题的处理过程与对原问题的处理过程是相同 的。所以，分治法处理问题的算法可以自然地写成一个递 归的过程。例：二分法查找、汉诺塔问题、八皇后问题、快速排序法 、归并排序法等。9.2.2贪心法 贪心法把构造可

6、行解的工作分阶段来完 成。在各个阶段，选择那些在某些意义下 是局部最优的方案，期望各阶段的局部最 优的选择带来整体最优。 戴克斯特拉的最短路径算法 Kruskal的求最小生成树算法 背包问题贪心法常常帮助我们得到一个次优解。对某些问题，只 有通过系统的、彻底的搜索才能得到最优解，从而使我 们求得最优解的代价甚高，但是只要求得一个与最优解 相差不多的次优解就可满足要求时，选用贪心法可以很 快地得到较好的解。例9.9 背包问题：给定个物体和一个背包，已知物体的重量为i，背包能容纳物体的重量为。要求确定一组分数i（i），把物体的i部分放入背包，使得 最大（i也是已知的，是物体的总价格），即将尽量多的

7、价值装入背包。9.2.3动态规划法在求解某些问题的时候，可以试着把问题分成必要多的 子问题，每个子问题又可以分成数目不确定的必要多的 子子问题，这样就会产生大量的子问题。如果分得的子 问题界限不清，互相交叉，则在大量的子问题中会存在 一些完全相同的子问题，为了避免界重复解这些相同的 子问题，可以在解决一个子问题后把它的解保留下来， 若遇到求解与之相同的子问题的时候，就可以把它找出 来直接使用。为解问题而将它的子问题的解填入表中以 待需要时查表，这样的方法就是动态规划法。例9.11 给定一个多边形和各顶点的坐标。要求产生一组互 不相交的弦（不相邻顶点间的连线），将此多边形划分成若 干三角形，使得

8、弦的总长最小。图9.2给出了一个七边形。用动态规划法来解此问题，可作如下分析：如果找到一种 划分，因为要求弦互不相交，所以任何一边，必定与某一 顶点构成一个三角形，例如边()必定属于某，这里的是，中的某个值。将此七边形分割成两个部分：一部分是多边形；另一部分是多边形。一般地 ，用表示从开始连续个顶点所构成的多边形， 表示边形的一种划分所产生的弦的总长， （，）表示到之间的弦长，则有以下等式 ：本书所见过的运用动态规划法的算法有：所有结点间的 最短路径算法（算法8.5）及最佳二叉排序树的构造算法 （参看算法6.8）。9.2.4回溯算法有一些问题，要求找到一组解，或要求找 到一个满足某些条件的最优

9、解。对于解决 这样的问题，可以通过使用彻底的搜索方 法来解决。然而，彻底的搜索，要进行大 量的比较，大量的舍弃，要以大量的运算 时间为代价，对于这种情况使用回溯算法 可以大大减少搜索的次数，八皇后问题迷宫问题深度优先周游树或图例9.12 四色问题：给定图9.5，其中， ，标明七个区域，要求用不多于四种颜色对这七 个区域进行着色，使得有公共界的区域不同色应用回溯方法解问题时，这问题的解须能表示为一个 元组。例 骑士周游问题。给定一个的方阵，共有个 区域，有一个国际象棋的马置于一个区域上，要求找到 一条路径，使马按国际象棋的允许走法，从开始区域出 发，不重复地把个区域都恰好经过一次。一般回溯方法的

10、程序结构。 void 函数名 (void) 准备初值； do while (范围未超界并且工作未完成) 分析条件；/* 保证不满足条件不往下去 */ if (成功) 进堆栈； 由第一选择开始进入下一层次 else 本层更换选择； /* 横向走 */ if ( 工作未完成 ) 弹出堆栈； 原来的上一层更换为下一选择； /* 回溯，上层横向走 */ while ( 全部工作完成 ) ； 输出； 小 结 分治法通过把问题化为较小的问题来解 决原问题，简化或减少了对题目的运算； 贪心法通过分阶段地挑选，最快地得到 较好的解； 动态规划法用填表的方法避免了大量重 复的计算； 回溯法跳过大量无须测试的元组

11、很快地 得到最优解。有时对同一个问题，可以使用不同的算法来实现：例 0/1背包问题：给定个物体和一个背包，已知物体的重量为i，背包能容纳物体的重量为。要求确定一组分数i（限制i取0和两个值），把物体的i部分放入背包，使得 最大（i也是已知的，是物体的总价格），即将尽量多的价值装入背包。（1）用分治法来做。数组1n按/值的递增的顺 序存放物体的重量，1n放对应物体的价格，x1 n是解向量。给定背包能放的总重量，求解时可以把它分为 两种情况：一种是如果n，则化为求解对前n-1个物 体的0/1背包问题，即xn取0；另一种是如果n，则 xn取1，问题化为对能容纳重量为-n的背包和前n-1 个物体的背包问题。所以，可把原问题化为子问题，用递归 的方式解。 （2）用动态规划法来解。也分成上述的两种情况。设fn() 为所求，则它可由如下的递推式得到：将改成，从变到，上式变为：在时，取fi()。从0()0开始，顺序地将 1，2，n填表，得到它的最优解fn。这时对的存放 顺序没有要求。（3）用回溯的方法解这个问题。通过构造解答树的方式 来实现。一个算法中，也可以结合使用几种算法设计技巧。如快 速排序算法是分治的技巧和回溯的技巧的结合，其中分 治的技巧是主要的。