文档介绍：第九章算法分析与设计
算法分析技术
算法设计技术
1
张乃孝算法与数据结构——C语言描述
算法分析技术
评价一个算法的好坏,主要看执行算法时所需要占用的计算机空间的大小和计算过程需要花费的计算机CPU时间的多少。因此,算法的分析主要包含时间和空间两个方面。

空间代价分析
时间代价分析
2
张乃孝算法与数据结构——C语言描述
空间代价分析
根据算法执行过程中对存储空间的使用方式,我们又把对算法空间代价分析分成两种情形:静态分析和动态分析。
1. 静态分析
一个算法静态使用的存储空间,是指在算法执行前,可以通过对程序静态的分析确定的使用空间,称为静态空间。
在静态空间分析中,值得注意的是数组(静态数组),它占用了大部分静态空间。
3
张乃孝算法与数据结构——C语言描述
2. 动态分析
一个算法在执行过程中以动态方式使用的存储空间是指在算法执行过程中动态分配的存储空间,它们从程序的表面形式上不能完全确定,我们把在算法执行过程中才能确定的空间称为动态空间。
动态空间的确定主要由两种情况构成:(1)函数的递归;(2)调用动态分配(malloc)和回收(free)函数。
4
张乃孝算法与数据结构——C语言描述
快速排序是一递归过程,调用该过程时,需分配的空间包括局部变量i,j和temp,形式参数1,r和被排序的对象等。被排序对象用指针方式传递,调用时不必动态开辟新的空间,只须少量空间存放实参的地址等信息,所以递归调用时动态分配的空间与待排序记录的个数n无关,为一常量。递归深度h最大等于n,这时动态空间代价为O(n),若每次都选较短的部分先处理,则递归深度不会超过log2n,这时动态空间代价即为O(log2n)()。这里实际被排序对象的空间应算静态空间,显然是O(n)。
(1)函数的递归
5
张乃孝算法与数据结构——C语言描述
(ⅰ)没有使用free函数
此时,动态空间代价为O(k),k为使用malloc的次数。
(ⅱ)使用free函数
不能简单的用malloc使用的次数减去free的使用次数作为动态空间的代价,应从malloc和free的具体执行情况来分析。
由书中(P284)算法进行动态空间代价分析,整个算法使用的动态空间代价为
(2)调用动态分配和回收函数。
6
张乃孝算法与数据结构——C语言描述
时间代价分析
算法的执行时间绝大部分花在循环和递归上
1. 循环
循环语句的时间代价一般用以下三条原则分析:
(3)对于多层嵌套循环,一般可按大O表示法的乘法规则计算。但如果嵌套是有条件的,为精确计算其时间代价,要仔细累加循环中简单语句的实际执行数目,以确定其时间代价。
(1)对于一个循环,循环次数乘以每次执行简单语句的数目即为其时间代价。
(2)对于多个并列循环,可先计算每个循环的时间代价,然后按大O表示法的加法规则计算总代价。
7
张乃孝算法与数据结构——C语言描述
求无回溯的匹配算法的时间代价()。
解问题规模:模式串长度m,目标串长度n(n>m)。
算法中有一个循环,在分析时应从算法执行效果具体分析。
因为i+1与j+1顺序执行,循环中j只增不减,循环条件为i<m且j<n,所以j+1最多执行n次,i+1也最多执行n次。又因为next[i]<i,且循环过程中i始终大于等于0,所以i:= next[i]最多执行n次,总的时间代价为O(n)。
8
张乃孝算法与数据结构——C语言描述

对于递归算法,一般可把时间代价表示为一个递归方程。解这种递归方程最常用的方法是进行递归扩展,通过层层递归,直到递归出口,然后再进行化简。
下面给出一类递归方程的求解方法。设递归方程为:
9
张乃孝算法与数据结构——C语言描述
递归扩展过程如下:
10
张乃孝算法与数据结构——C语言描述