MENU

算法的时空复杂度分析

2019 年 07 月 05 日 • 阅读: 90 • 算法

大 O 表示法

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

多项式量级复杂度

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

O(logn)

根据换底公式,logab=logcb/logca,logab=1/logba,有 log3n=log32 * log2n。可以看出,任意底的对数都可化为 C * log2n,所以,在对数阶复杂度表示法中,我们忽略对数的底,统一表示为 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 年 08 月 02 日