算法的时空复杂度分析

本文首发于 LOGI'S BLOG，由作者转载。

大 O 表示法

大 O 表示法并不具体表示代码的实际执行时间和实际占用空间，而代表代码执行时间和占用空间随数据规模增加的增长趋势，所以用大 O 表示法定义的时空复杂度分别叫做 渐进时间复杂度（Asymptotic /ˌæsimp'tɔtik,-kəl/ Time Complexity） 和 渐进空间复杂度（Asymptotic Space Complexity）。算法的空间复杂度计算相对容易，以下仅介绍时间复杂度。

多项式量级复杂度

复杂度根据量级可分为 多项式（Polynomial /ˌpɑlɪ'nomɪəl/） 和 非多项式量级（Non-Deterministic Polynomial），O(2ⁿ) 和 O(n!) 属于后者。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，甚至达到无限长，所以非多项式量级算法是不可接受的低效算法。

O(logn)

根据换底公式，log_ab=log_cb/log_ca，log_ab=1/log_ba，有 log₃n=log₃2 * log₂n。可以看出，任意底的对数都可化为 C*log₂n，所以，在对数阶复杂度表示法中，我们忽略对数的底，统一表示为 O(logn)。

O(m+n) 和 O(m*n)

如果算法的数据规模为多个变量，并且无法事先评估他们的大小，那么在表示时间复杂度时要把他们全部写出。

最好、最坏、平均和均摊时间复杂度

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个 2 倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来 array 数组中的数据依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 复制给 array，array 现在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 将 element 放到下标为 i 的位置，下标 i 加一
   array[i] = element;
   ++i;
}

上面这段代码是往数组尾插入元素，并且实现了自动扩容功能。在数组未满的情况下，直接放到数组尾即可，因此，最好时间复杂度为 O(1)。在数组满的情况下，需要进行 n 次移动，并申请 n 个空间，因此，最坏时间复杂度是 O(n)，最坏空间复杂度是 O(n)。

再看平均时间复杂度，总共有 n+1 种情况，其中数组未满有 n 种情况，每种的概率都是 1/n+1。数组满有 1 种情况，概率也是 1/n+1，所以平均时间复杂度为 (n * 1/n+1 + 1/n+1)/n+1 = O(1)。

最后计算 均摊时间复杂度，首先说明其概念和适用场景。对某个数据结构做一组连续操作，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，并且这些操作间存在前后连贯的时序关系，此时，我们便可将这组操作放在一起考虑，看能否将较高时间复杂度的那些操作耗时，平摊到其他低时间复杂度操作上，这种分析方法就叫做 摊还分析，通过摊还分析得到的时间复杂度，被称为均摊时间复杂度。一般情况下，能够应用均摊时间复杂度分析的场合，均摊复杂度等于最好时间复杂度。

对于上例，每一次 O(n) 的移动操作，都会跟着 n 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n 次耗时少的操作上，这一组连续操作的均摊时间复杂度就是 O(1)。

简要总结

最好时间复杂度计算简单，与此同时，参考意义也不是很大。最坏时间复杂度计算较为复杂，如用于关键环节需要重点考虑。平均时间复杂度计算最为复杂，也是最常用的评价指标，而可以使用摊还分析的算法，使用均摊时间复杂度代替常规的加权平均/期望得出的平均复杂度更具实际意义。

参考文献

最后编辑于：2019.07.05 22:28:14