Apr 26, 2013 – 学习 & 提升 – 程序设计  学习笔记   – Bai

算法时间复杂度分析

程序 P 所需时间 T(P) 是其编译时间和运行(或执行)时间的总和。由于编译时间不依赖于问题实例的特征(比如问题规模),所以编译时间一般都是固定的。此外,一旦已经证实了程序可以正常运行,就可以多次执行而不需要重新编译,所以,真正关心的是程序的执行时间。

但是确定程序的执行时间也不是一件容易的事,因为它受多方面的影响,比如说硬件、软件平台等,相同的算法在不同的硬件机器上执行,所消耗的时间是不同的。即使是在同一台机器上,一个算法在不同的时间执行,所消耗的时间也是不同的(当某个时刻计算机系统待处理的任务比较多时,这个时刻算法执行消耗的时间相对于计算机系统待处理任务较少时,所用的时间可能会多些)。我们使用“时间复杂度”并不是为了计算算法执行所消耗的时间,而是用于评定不同的算法之间在时间成本上,那个消耗的时间理论上少些,那个多些。对于某一具体问题的不同算法 A 和 B,经过“时间复杂度”的理论分析,通常情况下,如果算法 A 在时间成本上比算法 B 消耗的时间要少,那么在实际运行中算法 A 的执行会比算法 B 快。注意这里是通常情况下的结果,因为毕竟实际情况比较复杂,而且任何情况都有特殊的时候,但是,就平均上而言,特殊毕竟是少数,大部分都是正常情况的,所以时间复杂度的理论分析和实际的运行效果都是一致的。因此,算法的时间复杂度分析对于程序的评估具有非常重要的作用。

一些术语

算法的消耗时间

一个算法执行所消耗的时间等于算法中所有语句执行的时间之和。

单位时间

如果我们不考虑机器的软,硬件差别,假定语句执行一次所消耗的时间一样,并把语句执行一次所消耗的时间定义为单位时间。这样的假定有助于我们理解,并能把问题集中在需要考虑的地方。

语句频度

语句频度是指算法中语句的执行次数。

那么,算法中每条语句的执行时间 = 该语句的执行次数(语句频度) * 单位时间

所以,一个算法执行所消耗的时间 = 算法中所有语句的语句频度 * 单位时间

例如,求两个 n 阶方阵 C=A*B 的乘积,其算法如下:

 1     void MatrixMultiply (int A[n][n]int B[n][n]int C[n][n])
 2     {
 3        for(i=0; i < n; i++)           //1+(n+1)+n
 4        {
 5           for (j=0;j < n; j++)        //n*(1+(n+1)+n)
 6           {
 7              C[i][j]=0;               //n^2
 8              for (k=0; k < n; k++)    //n^2 * (1+(n+1)+n)
 9              {
10                C[i][j]=C[i][j]+A[i][k]*B[k][j]; //n^3
11              }
12           }
13        }
14     }

则算法所有语句的频度之和为:

T(n) = 3n3 + 5n2 + 4n + 2

算法的执行时间 = T(n) * 单位时间。设单位时间为 1, 则算法执行时间等于 T(n)。可以看出法 MatrixMultiply 的执行时间 T(n) 是一个关于矩阵阶数 n 的函数。

问题规模

在上面的算法执行时间 T(n) 是一个关于 n 的函数,n 称为"问题规模"。"问题规模"(这里是 n )与算法的执行次数有关,在上面的例子中,n 越大,算法的执行次数越多。一般情况下,算法中基本操作重复执行的次数是问题规模 n 的某个函数,用 T(n) 表示。

渐进时间复杂度

对于语句频度 T(n),若有某个辅助函数 f(n),使得当 n 趋近于无穷大时,T(n)/f(n) 的极限值为不等于零的常数,则称 f(n) 是 T(n) 的同数量级函数,记作 T(n) = O(f(n)),称 O(f(n)) 为算法的渐进时间复杂度( O 是数量级的符号),它表示随问题规模n的增大,算法执行时间的增长率和 f(n) 的增长率相同。渐进时间复杂度就是我们常说的时间复杂度。

对于上面的 MatrixMultiply 算法来说,其算法频度为:T(n)=2n3 + 3n2 + 2n + 1,可以很容易的得出,f(n)=n3 ,因此,此算法的时间复杂度为 O( n3 )。

最坏时间复杂度

最坏情况下的时间复杂度称最坏时间复杂度。算法的时间复杂度不仅与语句频度有关,还与问题规模及输入实例中各元素的取值有关。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何更长。

时间复杂度的计算步骤

  1. 计算出算法中基本操作的总的执行次数,即算法的频度 T(n)。

  2. 计算出 T(n) 的数量级

求 T(n) 的数量级,只要将 T(n) 进行以下一些操作:忽略常量、低次幂以及最高次幂的系数。令 f(n)=T(n) 的数量级。

  1. 用大 O 来表示时间复杂度

当 n 趋近于无穷大时,如果 lim(T(n)/f(n)) 的值为不等于 0 的常数,则称 f(n) 是 T(n) 的同数量级函数。记作 T(n)=O(f(n))。

一些示例

1     int num1, num2;
2     for(int i=0; i<n; i++) { 
3       num1 += 1;
4       for(int j=1; j<=n; j*=2) { 
5          num2 += num1;
6       }
7     }

分析:

1、计算算法的频度 T(n)

语句 int num1, num2; 的频度为 1;

语句 i=0; 的频度为 1;

语句 i<n;i++; num1+=1; j=1; 的频度为 n(事实上,语句 i<n; 的频度为 n+1,下同);

语句 j<=n; j*=2; num2+=num1; 的频度为 n*log2n;

因此,T(n) = 2 + 4n + 3n*log2n

2、计算出 T(n) 的数量级

忽略掉 T(n) 中的常量、低次幂和最高次幂的系数,得:f(n) = n*log2n。

3、用大 O 来表示时间复杂度

lim(T(n)/f(n)) = (2+4n+3n*log2n) / (n*log2n) = 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3

当 n 趋向于无穷大,1/n 趋向于 0,1/log2n 趋向于 0,所以极限等于 3。

因此,T(n) = O(n*log2n)。

时间复杂度计算的简化步骤

由上例分析可以看出,决定算法复杂度的是执行次数最多的语句,这里是 num2 += num1,一般也是最内循环的语句。于是,以上步骤可以简化为:

  1. 找到执行次数最多的语句;

  2. 计算该语句执行次数的数量级;

  3. 用大 O 来表示结果。

继续以上述算法为例,进行分析:

1、执行次数最多的语句为 num2 += num1。

2、T(n) = n*log2n,f(n) = n*log2n。

3、lim(T(n)/f(n)) = 1,T(n) = O(n*log2n)。

一些计算规则

1)加法规则。T(n,m) = T1(n) + T2(m) = O (max ( f(n), g(m) )

2)乘法规则。T(n,m) = T1(n) * T2(m) = O (f(n) * g(m))

3)特例。在大 O 表示法里面有一个特例,如果 T1(n) = O©, c 是一个与 n 无关的任意常数,T2(n) = O ( f(n) ) 则有 T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) )。

也就是说,在大O表示法中,任何非0正常数都属于同一数量级,记为 O(1)。

常见的时间复杂度

常见的时间复杂度依次为:常数阶 O(1)、对数阶 O(log2n)、线性阶 O(n)、线性对数阶 O(nlog2n)、平方阶 O(n2 )、立方阶 O(n3 )、k 次方阶 O(nk )、指数阶 O(2n )。

它们的效率关系为:

c < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! (c是一个常量)

较好的复杂度为前四个,后三个较差,稍微大一些的 n 就会令这个算法几乎停滞。

几个常见复杂度示例

O(1)

交换 i 和 j 的内容:

temp=i;
i=j;
j=temp;                    

以上三条单个语句的频度为 1,该程序段的执行时间是一个与问题规模 n 无关的常数。算法的时间复杂度为常数阶,记作 T(n)=O(1)。如果算法的执行时间不随着问题规模 n 的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是 O(1)。

O(n)

a=0;
b=1;
for (i=1;i<=n;i++) {  
  s=a+b;
  b=a;  
  a=s;
}

一般单个循环的复杂度为 O(n)。

O(long2n)

i=1;
while (i<=n)
  i=i*2;

O(n2 )

sum=0;
for(i=1;i<=n;i++)      
   for(j=1;j<=n;j++) 
     sum++;

一般双层循环的复杂度为 O(n2 )。

O(n3 )

for(i=0;i<n;i++)
{  
  for(j=0;j<i;j++)  
  {
     for(k=0;k<j;k++)
        x=x+2;  
  }
}

一般三层循环的复杂度为 O(n3 )。

上一篇:

下一篇:

回顶部