算法与数据结构(c语言) 第10章 算法分析与设计ppt课件.ppt

《算法与数据结构(c语言) 第10章 算法分析与设计ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章算法分析与设计读者在学习以前各章的基础上，系统地阅读本章，可对算法的设计和分析技术有一个鸟瞰，以便于将本书所学到的算法归类整理，达到开阔思路，提高观点，增强兴趣的目的。目录10.1算法分析技术10.1.1空间代价分析10.1.2时间代价分析10.2算法设计技术10.2.1分治法10.2.2贪心法10.2.3动态规划法10.2.4回溯法10.2.5分枝界限法与0/1背包问题*10.1算法分析技术评价一个算法的代价，主要看执行算法时所需要占用的计算机空间的大小和计算过程需要花费的计算机CPU时间的多少。算法的分析主要包含时间和空间两个方面。10.1.1空间代价分析根据算法执行

2、过程中对存储空间的使用方式，可以把对算法空间代价分析分成两种：静态分析和动态分析。一个算法静态使用的存储空间，称为静态空间。静态分析的方法比较容易，只要求出算法中使用的所有变量的空间，再折合成多少空间存储单位即可。静态分析例10.1直接插入排序的空间代价分析（参看算法8.1）被排序的记录的个数ｎ决定了问题的规模。被排序的对象在调用函数中申请，并用一个指针变量pvector传递给被调函数，空间大小显然是O(n)；在排序程序中，算法以静态方式定义了两个整型变量i和j、一个存储插入元素的临时变量temp，所以在算法中分配的空间为一个常量，记为O(1)（对于常量c而言，O(c)与O(1

3、)为相同复杂度）。动态分析一个算法在执行过程中，必须以动态方式分配的存储空间是指在算法执行过程中才能分配的空间称为动态空间。动态空间的确定主要由两种情况构成：（1）函数的递归；（2）执行动态分配函数。对于递归函数而言，由于每次调用需要分配不同的运行空间，所以递归函数的空间代价，不能简单地采用静态分析方法。假设静态分析一个递归函数的空间代价为一个常量c，如果递归深度为ｈ（h的大小依赖于程序的动态执行），动态空间代价应该为C*h。函数的递归调用例10.2快速排序（参看算法8.8）对函数静态分析的空间与待排序记录的个数ｎ无关，为一常量。递归深度ｈ最大等于ｎ，这时动态空间代价为O(n)

4、；若每次都选较短的部分先处理，则递归深度不会超过log2n，这时动态空间代价即为O(log2n)。一个函数（或过程）如果使用了malloc和free函数，malloc和free所开辟、释放的空间只能在算法执行过程中加以确定，这些空间属于动态空间。下面的讨论中，假设每次分配的空间与问题规模无关，只是一个常数C。执行动态分配函数没有使用free函数动态空间代价为O(k)，k为使用malloc的次数（包括在循环和递归调用中动态执行的次数）。分如下两种情况讨论：使用free函数设free使用次数为j。令：ｃ0＝１，pi（i=1..j）为第i-1次使用free和ｉ次使用free之间执行m

5、alloc的次数。用公式ｃi=ｃi-1+pi-1可以计算出在第i-1次使用free和第i次使用free（i=1..j）之间使用的最大动态空间数。再定义j’如下：于是整个算法使用的动态空间代价为：例10.3一个算法执行过程中malloc和free顺序为（ｎ代表malloc，ｄ代表free）。ｎｎｎｄｄｎｄｄｎｎｎｄｎｄｄ,j＝j’＝７Ｃ0=１，Ｃ1＝３，Ｃ2＝２，Ｃ3＝２，Ｃ4＝１，Ｃ5＝３，Ｃ6＝３，Ｃ7＝２。10.1.2时间代价分析算法的执行时间绝大部分花在循环和递归上。循环循环语句的时间代价一般用以下三条原则分析：（１）　对于一个循环，循环次数乘以每次执行简单语句的数目即为

6、其时间代价。（２）　对于多个并列循环，可先计算每个循环的时间代价，然后按大Ｏ表示法的加法规则计算总代价。（３）对于多层嵌套循环，一般可按大Ｏ表示法的乘法规则计算。但如果嵌套是有条件的，为精确计算其时间代价，要仔细累加循环中简单语句的实际执行数目，以确定其时间代价。例10.5求带权图中每一对结点之间的最短路径的算法的时间代价（参看算法9.7）。解问题规模：带权图顶点数目为ｎ。算法中共有五个循环，前两个循环与后三个是并列关系。前两个循环是嵌套关系，后三个之间也是嵌套关系。最内层循环的时间代价为一常数C，则前两个循环时间代价为：后三个循环时间代价为：所以总的时间代价为O(n3)。例

7、10.6为实现无回溯的匹配，而要计算模式串的NEXT数组算法的时间代价（参看算法3.8）。问题规模：模式串长度ｍ。从形式上来看，这是一个二重循环，每重循环最多执行m次，最大运行时间可能达到O(m2)。仔细分析：因为每执行一次外层（第4行）循环，i严格增1（第6行），所以外层循环正好执行m－1次；但是，k的值从（第2行）-1开始，k++恰好执行（第6行）m－1次，并且只有在这一语句中k被增值。而在内层循环（第5行）中，语句k＝next[k]至少使k减少1，整个算法中，这个语句的执行次数累计起来