算法时间复杂度分析
程序 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 )。
最坏时间复杂度
最坏情况下的时间复杂度称最坏时间复杂度。算法的时间复杂度不仅与语句频度有关，还与问题规模及输入实例中各元素的取值有关。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何更长。
时间复杂度的计算步骤
计算出算法中基本操作的总的执行次数，即算法的频度 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))。
一些示例
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，一般也是最内循环的语句。于是，以上步骤可以简化为：
找到执行次数最多的语句；
计算该语句执行次数的数量级；
用大 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 )。
上一篇： aria2：高速下载工具
下一篇：打工是最愚蠢的投资