《第九章算法分析与设计》由会员分享,可在线阅读,更多相关《第九章算法分析与设计(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)用回溯的方法解这个问题。通过构造解答树的方式 来实现。一个算法中,也可以结合使用几种算法设计技巧。如快 速排序算法是分治的技巧和回溯的技巧的结合,其中分 治的技巧是主要的。