第九章 算法分析与设计.ppt

《第九章 算法分析与设计.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第九章算法分析与设计9.1算法分析技术9.2算法设计技术1张乃孝算法与数据结构——C语言描述9.1算法分析技术评价一个算法的好坏，主要看执行算法时所需要占用的计算机空间的大小和计算过程需要花费的计算机CPU时间的多少。因此，算法的分析主要包含时间和空间两个方面。9.1.1空间代价分析9.1.2时间代价分析2张乃孝算法与数据结构——C语言描述9.1.1空间代价分析根据算法执行过程中对存储空间的使用方式，我们又把对算法空间代价分析分成两种情形：静态分析和动态分析。1.静态分析一个算法静态使用的存储空间，是指在算法执行前，可以通过对程序静态的分析确定的使用空间，称为静态空间。在静态空间分

2、析中，值得注意的是数组（静态数组），它占用了大部分静态空间。3张乃孝算法与数据结构——C语言描述2.动态分析一个算法在执行过程中以动态方式使用的存储空间是指在算法执行过程中动态分配的存储空间，它们从程序的表面形式上不能完全确定，我们把在算法执行过程中才能确定的空间称为动态空间。动态空间的确定主要由两种情况构成：（1）函数的递归；（2）调用动态分配（malloc）和回收（free）函数。4张乃孝算法与数据结构——C语言描述例9.2快速排序是一递归过程，调用该过程时，需分配的空间包括局部变量ｉ，ｊ和temp，形式参数１，ｒ和被排序的对象等。被排序对象用指针方式传递，调用时不必动态开辟新

3、的空间，只须少量空间存放实参的地址等信息，所以递归调用时动态分配的空间与待排序记录的个数ｎ无关，为一常量。递归深度ｈ最大等于ｎ，这时动态空间代价为O(n)，若每次都选较短的部分先处理，则递归深度不会超过log2n，这时动态空间代价即为O(log2n)（参看算法7.9）。这里实际被排序对象的空间应算静态空间，显然是O(n)。（1）函数的递归5张乃孝算法与数据结构——C语言描述（ⅰ）没有使用free函数此时，动态空间代价为O(k)，k为使用malloc的次数。（ⅱ）使用free函数不能简单的用malloc使用的次数减去free的使用次数作为动态空间的代价，应从malloc和free的具

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

5、张乃孝算法与数据结构——C语言描述例9.6求无回溯的匹配算法的时间代价（参看算法3.6）。解　问题规模：模式串长度ｍ，目标串长度ｎ（ｎ＞ｍ）。算法中有一个循环，在分析时应从算法执行效果具体分析。因为ｉ＋１与ｊ＋１顺序执行，循环中ｊ只增不减，循环条件为ｉ＜ｍ且ｊ＜ｎ，所以ｊ＋１最多执行ｎ次，ｉ＋１也最多执行ｎ次。又因为next[i]＜ｉ，且循环过程中ｉ始终大于等于０，所以i:=next[i]执行ｎ次，总的时间代价为O(n)。8张乃孝算法与数据结构——C语言描述2．递归对于递归算法，一般可把时间代价表示为一个递归方程。解这种递归方程最常用的方法是进行递归扩展，通过层层递归，直到递归出口

6、，然后再进行化简。下面给出一类递归方程的求解方法。设递归方程为：9张乃孝算法与数据结构——C语言描述递归扩展过程如下：10张乃孝算法与数据结构——C语言描述设ｎ＝ｂk，则又设d(x)为“积性函数”即：，则有：11张乃孝算法与数据结构——C语言描述以下分三种情况讨论：（1）ａ＞d(b)，则12张乃孝算法与数据结构——C语言描述（2）ａ＜d(b)，则13张乃孝算法与数据结构——C语言描述（3）ａ＝d(b)，则14张乃孝算法与数据结构——C语言描述9.2算法设计技术9.2.1分治法9.2.2贪心法9.2.3动态规划法9.2.4回溯法9.2.5分枝界限法15张乃孝算法与数据结构——C语言描

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