时间复杂度

本文是对时间复杂度更加深入了解。

时间频度

我们知道一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。

通常一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

时间复杂度

在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，引入了时间复杂度的概念。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，$\frac{T(n)}{f(n)}$的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n) =O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1)；另外，在时间频度不相同时，时间复杂度有可能相同，如 $T(n)=n^2+3n+4$ 与 $T(n)=4n^2+2n+1$ 它们的频度不同，但时间复杂度相同，都为$O(n^2)$。

简单来说，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

例如：

for(i=1; i <= n; ++i)
{
    for(j=1; j <= n; ++j)
    {
        // 该步骤属于基本操作执行次数： n^2
        c[i][j] = 0;
        // 该步骤属于基本操作执行次数：n^3
        for(k=1; k <= n; ++k)
            c[i][j] += a[i][k] * b[k][j];
    }
}

则有 $T(n)=n^3 + n^2$ ，根据上面括号里的同数量级，我们可以确定 $n^3$ 为 $T(n)$ 的同数量级；
则有 $f(n)=n^3$ ，然后根据 $\frac{T(n)}{f(n)}$ 求极限可得到常数c；
则该算法的时间复杂度：$T(n) = O(n^3)$

空间复杂度

空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) , 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。

常见时间复杂度

按数量级递增排列，常见的时间复杂度有：

1. 常数阶 $O(1)$ ：表示算法的运行时间为常量

2. 对数阶 $O(log_{2}n)$ ：二分查找算法

3. 线性阶 $O(n)$ ：表示该算法是线性算法

4. 线性对数阶 $O(nlog_{2}n)$

5. 平方阶 $O(n^2)$ ：对数组进行排序的各种简单算法，例如直接插入排序的算法；

   立方阶 $O(n^3)$ ：做两个n阶矩阵的乘法运算 ；... k次方阶 $O(n^k)$

6. 指数阶 $O(2^n)$ ：求具有n个元素集合的所有子集的算法

7. $O(n!)$：求具有N个元素的全排列的算法

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

时间复杂度比较(优<...<劣) ： $O(1)$ < $O(log_{2}n)$ < $O(n)$ < $O(n^2)$ < $O(n^3)$ < $O(2^n)$ ... < $O(n^k)$ < $O(2^n)$

时间复杂度的例子

1. 时间复杂度：$O(1)$

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

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作 $T(n)=O(1)$。

如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是 $O(1)$。

2. 时间复杂度：$O(n^2)$

// 1
sum=0; 
for (i = 1; i <= n; i++){ 
    for(j = 1;j <= n; j++){ 
        // 该步骤属于基本操作执行次数：n^2
        sum++；
    }
}                      

上列计算结果：$T(n) = n^2 + 1 = O(n^2)$

for (i = 1; i < n; i++){
    // n-1
    y = y + 1; 
    for (j = 0;j <= (2 * n); j++){
        // (n-1)*(2n+1) = 2n^2-n-1
        x++; 
    }     
}   

上列计算结果：

$f(n)=2n^2-n-1+(n-1) = 2n^2-2$

$T(n)=O(n^2)$

3. 时间复杂度：$O(n)$

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

上列计算结果：$T(n )= 2+3n = O(n)$

4. 时间复杂度：$O(log_{2}n)$

// 1
i = 1; 
while ( i <= n){
    // 2^f(n) <= n; f(n) <= log2n 
    i = i * 2;  
}   

上列计算结果：$T(n)=O(log2n)$

5. 时间复杂度：$O(n^3)$

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

当i = m，j = k的时候，内层循环的次数为k ，
当i = m时，j可以取 0, 1, ... , m-1,所以这里最内循环共进行了 $0+1+...+m-1=\frac{(m-1)m}{2}$ 次,
所以，i从0取到n，则循环共进行了：$0+(1-1) \frac{1}{2}+...+(n-1)\frac{n}{2} = \frac{n(n+1)(n-1)}{2}$ 次,

$T(n) = \frac{n(n+1)(n-1)}{2} = \frac{(n^3-n)}{2}$

$f(n) = n^3$

所以时间复杂度为 $O(n^3)$。

总结

定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为$T(n)$，它是n的某一函数 $T(n)$ 称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果$f(n)=O(n)$，那显然成立$f(n)=O(n^2)$，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

大O记法：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的 “O” 表示量级 (order)，比如说 “二分检索是 $O(log_{2}n)$ 的”，也就是说它需要 “通过$O(log_{2}n)$量级的步骤去检索一个规模为n的数组” 。记法 $O ( f(n) )$ 表示当 n增大时，运行时间至多将以正比于 $f(n)$ 的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的 $O(n^2)$ 算法在n较小的情况下可能比一个高附加代价的 $O(nlog_{2}n)$ 算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

参考

1. 百科·时间复杂度 (opens new window)
2. Python之路,Day21 - 常用算法学习 (opens new window)