算法分析
．评价算法好坏的标准
求解同一计算问题可能有许多不同的算法究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？
选用的算法首先应该是正确的此外主要考虑如下三点
① 执行算法所耗费的时间
② 执行算法所耗费的存储空间其中主要考虑辅助存储空间
③ 算法应易于理解易于编码易于调试等等
．算法性能选择一个占存储空间小运行时间短其它性能也好的算法是很难做到的原因是上述要求有时相互抵触要节约算法的执行时间往往要以牺牲更多的空间为代价而为了节省空间可能要耗费更多的计算时间因此我们只能根据具体情况有所侧重
① 若该程序使用次数较少则力求算法简明易懂
② 对于反复多次使用的程序应尽可能选用快速的算法
③ 若待解决的问题数据量极大机器的存储空间较小则相应算法主要考虑如何节省空间
．算法的时间性能分析（）算法耗费的时间和语句频度
一个算法所耗费的时间=算法中每条语句的执行时间之和
每条语句的执行时间=语句的执行次数(即频度(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＜n;j++) n+
() for (j=;j＜n;j++) { n(n+)
() C[i][j]=; n
() for (k=; k＜n; k++) n(n+)
() C[i][j]=C[i][j]+A[i][k]*B[k][j]; n
}
}
该算法中所有语句的频度之和(即算法的时间耗费)为
T(n)=n+n+n+ ()
分析
语句()的循环控制变量i要增加到n测试到i=n成立才会终止故它的频度是n+但是它的循环体却只能执行n次语句()作为语句()循环体内的语句应该执行n次但语句()本身要执行n+次所以语句()的频度是n(n+)同理可得语句()()和()的频度分别是nn(n+)和n
算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数
（）问题规模和算法的时间复杂度
算法求解问题的输入量称为问题的规模(Size)一般用一个整数表示
【例．】矩阵乘积问题的规模是矩阵的阶数
【例．】一个图论问题的规模则是图中的顶点数或边数
一个算法的时间复杂度(Time Complexity 也称时间复杂性)T(n)是该算法的时间耗费是该算法所求解问题规模n的函数当问题的规模n趋向无穷大时时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度
【例．】算法MatrixMultidy的时间复杂度T(n)如()式所示当n趋向无穷大时显然有
这表明当n充分大时T(n)和n之比是一个不等于零的常数即T(n)和n是同阶的或者说T(n)和n的数量级相同记作T(n)=(n)是算法MatrixMultiply的渐近时间复杂度
数学符号的严格的数学定义
若T(n)和f(n)是定义在正整数集合上的两个函数则T(n)=(f(n))表示存在正的常数C和n使得当n≥n时都满足≤T(n)≤C·f(n)
（）渐进时间复杂度评价算法时间性能
主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能
【例．】有两个算法A和A求解同一问题时间复杂度分别是T(n)=nT(n)=n
（）当输入量n＜时有T(n)＞T(n)后者花费的时间较少
（）随着问题规模n的增大两个算法的时间开销之比n/n=n/亦随着增大即当问题规模较大时算法A比算法A要有效地多
它们的渐近时间复杂度(n)和(n)从宏观上评价了这两个算法在时间方面的质量在算法分析时往往对算法的时间复杂度和渐近时间复杂度不予区分而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度其中的f(n)一般是算法中频度最大的语句频度
【例．】算法MatrixMultiply的时间复杂度一般为T(n)=(n)f(n)=n是该算法中语句()的频度下面再举例说明如何求算法的时间复杂度
【例．】交换i和j的内容
Temp=i;
i=j;
j=temp;
以上三条单个语句的频度均为该程序段的执行时间是一个与问题规模n无关的常数算法的时间复杂度为常数阶记作T(n)=O()
如果算法的执行时间不随着问题规模n的增加而增长即使算法中有上千条语句其执行时间也不过是一个较大的常数此类算法的时间复杂度是O()
【例．】变量计数之一
() x=;y=;
() for(k;k<=n;k++)
() x++;
() for(i=;i<=n;i++)
() for(j=;j<=n;j++)
() y++;
一般情况下对步进循环语句只需考虑循环体中语句的执行次数忽略该语句中步长加终值判别控制转移等成分因此以上程序段中频度最大的语句是()其频度为f(n)=n所以该程序段的时间复杂度为T(n)=(n)
当有若干个循环语句时算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的
【例．】变量计数之二
() x=;
() for(i=;i<=n;i++)
() for(j=;j<=i;j++)
() for(k=;k<=j;k++)
() x++;
该程序段中频度最大的语句是()内循环的执行次数虽然与问题规模n没有直接关系但是却与外层循环的变量取值有关而最外层循环的次数直接与n有关因此可以从内层循环向外层分析语句()的执行次数
则该程序段的时间复杂度为T(n)=(n/+低次项)=(n)
（）算法的时间复杂度不仅仅依赖于问题的规模还与输入实例的初始状态有关
【例．】在数值A[n]中查找给定值K的算法大致如下
()i=n;
()while(i>=&&(A[i]!=k))
() i;
()return i;
此算法中的语句()的频度不仅与问题规模n有关还与输入实例中A的各元素取值及K的取值有关:
①若A中没有与K相等的元素则语句()的频度f(n)=n
②若A的最后一个元素等于K则语句()的频度f(n)是常数
（）最坏时间复杂度和平均时间复杂度
最坏情况下的时间复杂度称最坏时间复杂度一般不特别说明讨论的时间复杂度均是最坏情况下的时间复杂度
这样做的原因是最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界这就保证了算法的运行时间不会比任何更长
【例．】查找算法【例·】在最坏情况下的时间复杂度为T(n)=(n)它表示对于任何输入实例该算法的运行时间不可能大于(n)
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下算法的期望运行时间
常见的时间复杂度按数量级递增排列依次为常数()对数阶(logn)线形阶(n)线形对数阶(nlogn)平方阶(n)立方阶(n)…k次方阶(nk)指数阶(n)显然时间复杂度为指数阶(n)的算法效率极低当n值稍大时就无法应用
类似于时间复杂度的讨论一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间它也是问题规模n的函数渐近空间复杂度也常常简称为空间复杂度算法的时间复杂度和空间复杂度合称为算法的复杂度
