()渐进时间复杂度评价算法时间性能
主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能
【例】有两个算法A 和A 求解同一问题时间复杂度分别是T (n)=n T (n)=n
()当输入量n<时有T (n)>T (n)后者花费的时间较少
()随着问题规模n的增大两个算法的时间开销之比n /n =n/亦随着增大即当问题规模较大时算法A 比算法A 要有效地多
它们的渐近时间复杂度O(n )和O(n )从宏观上评价了这两个算法在时间方面的质量在算法分析时往往对算法的时间复杂度和渐近时间复
杂度不予区分而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度其中的f(n)一般是算法中频度最大的语句频度
【例】算法MatrixMultiply的时间复杂度一般为T(n)=O(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)=O(n )
当有若干个循环语句时算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的
【例】变量计数之二
() x=;
() for(i=;i<=n;i++)
() for(j=;j<=i;j++)
() for(k=;k<=j;k++)
() x++;
该程序段中频度最大的语句是()内循环的执行次数虽然与问题规模n没有直接关系但是却与外层循环的变量取值有关而最外层循环的
次数直接与n有关因此可以从内层循环向外层分析语句()的执行次数
则该程序段的时间复杂度为T(n)=O(n /+低次项)=O(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)
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下算法的期望运行时间
常见的时间复杂度按数量级递增排列依次为常数()对数阶(log n)线形阶(n)线形对数阶(nlog n)平方阶(n )立方阶(n
)…k次方阶(n k )指数阶( n )显然时间复杂度为指数阶( n )的算法效率极低当n值稍大时就无法应用
类似于时间复杂度的讨论一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间它也是问题规模n的函数渐近空
间复杂度也常常简称为空间复杂度算法的时间复杂度和空间复杂度合称为算法的复杂度
