算法分析
评价算法好坏的标准
求解同一计算问题可能有许多不同的算法究竟如何来评价这些算法的好坏以便从中选出较好的算法呢?
选用的算法首先应该是正确的此外主要考虑如下三点
① 执行算法所耗费的时间;
② 执行算法所耗费的存储空间其中主要考虑辅助存储空间;
③ 算法应易于理解易于编码易于调试等等
算法性能选择
一个占存储空间小运行时间短其它性能也好的算法是很难做到的原因是上述要求有时相互抵触要节约算法的执行时间往往要以牺牲
更多的空间为代价;而为了节省空间可能要耗费更多的计算时间因此我们只能根据具体情况有所侧重
① 若该程序使用次数较少则力求算法简明易懂;
② 对于反复多次使用的程序应尽可能选用快速的算法;
③ 若待解决的问题数据量极大机器的存储空间较小则相应算法主要考虑如何节省空间
算法的时间性能分析
()算法耗费的时间和语句频度
一个算法所耗费的时间=算法中每条语句的执行时间之和
每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间
算法转换为程序后每条语句执行一次所需的时间取决于机器的指令性能速度以及编译所产生的代码质量等难以确定的因素
若要独立于机器的软硬件系统来分析算法的时间耗费则设每条语句执行一次所需的时间均是单位时间一个算法的时间耗费就是该算法中所
有语句的频度之和
【例】求两个n阶方阵的乘积 C=A×B其算法如下:
# define n // n 可根据需要定义这里假定为
void MatrixMultiply(int A[a]int B [n][n]int C[n][n])
{ //右边列为各语句的频度
int i j k;
() for(i=; i (2) for (j=0;j (3) C[i][j]=0; n 2
(4) for (k=0; k (5) C[i][j]=C[i][j]+A[i][k]*B[k][j]; n 3
}
}
该算法中所有语句的频度之和(即算法的时间耗费)为：
T(n)=2n 3 +3n 2 +2n+1 (1.1)
分析：
语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。tw.winGwit.Com故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循
环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n 2 ，n 2
(n+1)和n 3 。
算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。
(2)问题规模和算法的时间复杂度
算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。
【例3.4】矩阵乘积问题的规模是矩阵的阶数。
【例3.5】一个图论问题的规模则是图中的顶点数或边数。
一个算法的时间复杂度(Time Complexity, 也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模
n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。
【例3.6】算法MatrixMultidy的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有
这表明，当n充分大时，T(n)和n 3 之比是一个不等于零的常数。即T(n)和n 3 是同阶的，或者说T(n)和n 3 的数量级相同。记作T(n)=O(n 3
)是算法MatrixMultiply的渐近时间复杂度。
数学符号"O"的严格的数学定义：
若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤C·f(n)。
