算法时间复杂度分析

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

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

一些术语

算法的消耗时间

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

单位时间

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

语句频度

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

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

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

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

void MatrixMultiply (int A[n][n]，int B[n][n]，int C[n][n])
{
   for(i=0; i < n; i++)    //1+(n+1)+n
   {
      for (j=0;j < n; j++)    //n*(1+(n+1)+n)
  {
     C[i][j]=0;           //n^2
     for (k=0; k < n; k++)    //n^2 * (1+(n+1)+n)
     {
        C[i][j]=C[i][j]+A[i][k]*B[k][j]; //n^3
     }
  }
   }
}

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

T(n) = 3n³ + 5n² + 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)=2n³ + 3n² + 2n + 1，可以很容易的得出，f(n)=n³ ，因此，此算法的时间复杂度为 O( n³ )。

最坏时间复杂度

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

时间复杂度的计算步骤

计算出算法中基本操作的总的执行次数，即算法的频度 T(n)。
计算出 T(n) 的数量级

求 T(n) 的数量级，只要将 T(n) 进行以下一些操作：忽略常量、低次幂以及最高次幂的系数。令 f(n)=T(n) 的数量级。
用大 O 来表示时间复杂度

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

一些示例

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

分析：

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，一般也是最内循环的语句。于是，以上步骤可以简化为：

找到执行次数最多的语句；
计算该语句执行次数的数量级；
用大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)， 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(n² )、立方阶O(n³ )、k次方阶O(n^k )、指数阶O(2ⁿ )。

它们的效率关系为：

c < log2n < n < n*log2n < n² < n³ < 2ⁿ < 3ⁿ < 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(n² )

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

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

O(n³ )

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

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

Blog