数据结构与算法之美（一）：复杂度分析

本章内容源于笔者对极客时间《数据结构与算法之美》以下章节的学习笔记：

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。

为什么需要复杂度分析

把代码跑一遍，通过统计、监控得到算法执行的时间和占用的内存大小，这种方法称为事后统计法，有非常大的局限性：

1.测试结果非常依赖测试环境
2.测试结果受数据规模的影响很大

我们需要一个不用关心的宿主环境、不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。就是时间、空间复杂度分析法。

大O复杂度表示法

假设每行代码执行的时间都一样，为单位时间，所有代码的执行时间T(n)与每行代码的执行次数成正比。我们把这个规律总结成一个公式：T(n) = O(f(n))。

T(n)表示代码执行的时间
f(n)表示每行代码执行的次数总和
n表示数据规模的大小

这就是大O时间复杂度表示法。

注意：大O时间复杂度实际上并不代表真正的执行时间，表示代码执行时间随数据规模增长的变化趋势。公式中的低阶、常量、系数三部分并不左右增长趋势，所以忽略。

时间复杂度分析

时间复杂度全称渐进时间复杂度。分析技巧如下：

1.只关注循环执行次数最多的一段代码
2.加法法则：总复杂度等于量级最大的那段代码的复杂度
3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

强调一下，即便一段段代码循环10000次、100000次，只要是一个已知的数，跟n无关，照样也是常量级的执行时间。当n无限大的时候，就可以忽略。

以上三种复杂度的分析技巧不用刻意去记忆，实际上，复杂度分析这个东西关键在于“熟练”，多看案例多分析。

几种常见时间复杂度实例分析

常见复杂度量级并不多，以下几乎涵盖了今后接触的所有代码的复杂度量级。

复杂度量级	大O表达式	所属分类
常量阶	O(1)	多项式量级
对数阶	O(logn)	多项式量级
线性阶	O(n)	多项式量级
线性对数阶	O(nlogn)	多项式量级
平方阶	O(n²)	多项式量级
立方阶	O(n³)	多项式量级
k次方阶	O(n^k)	多项式量级
指数阶	O(2ⁿ)	非多项式量级
阶乘阶	O(n!)	非多项式量级

O(1)

只要代码的执行时间不随n的增大而增长，时间复杂度都记作O(1)。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

O(logn)、O(nlog)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。

i = 1;
while (i <= n) {
    i = i * 2;
}

以上代码中可以看出，变量i的值从1开始取，每循环一次就乘以 2，当大于n时，循环结束。i的取值是一个等比数列，求解2^x = n，x = log₂n。

类似的，log₃n = log₃2 * log₂n，不管是以2、3甚至是10为底，都可以转换为c * log₂n，忽略系数和对数的“底”，都记作O(logn)。

如果一段代码的时间复杂度是 O(logn) ，循环执行n遍，时间复杂度就是 O(nlogn) 了。

O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

O(m+n)、O(m*n)

代码的复杂度由两个数据的规模来决定。

空间复杂度分析

空间复杂度全称渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

空间复杂度分析比时间复杂度分析要简单很多。常见的空间复杂度就是O(1)、O(n)、O(n²)，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。

小结：复杂度包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系。越高阶复杂度的算法执行效率越低。常见复杂度从低阶到高阶有：
O(1)、O(logn)、O(n)、O(nlogn)、O(n² )。

复杂度分析的4个概念

最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。
最坏情况时间复杂度：代码在最糟糕情况下执行的时间复杂度。
平均情况时间复杂度：引入概率的概念，代码在所有情况下执行的次数的加权平均值。

实际上，在大多数情况下并不需要区分最好、最坏、平均情况时间复杂度。只有同一块代码在不同的情况下，时间复杂度有量级的差距，才会使用这三种复杂度表示法来区分。

均摊时间复杂度：利用摊还分析法将个别情况的高复杂度均摊到大部分情况的低复杂度所得到的时间复杂度。

应用场景：对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。

一般均摊时间复杂度就等于最好情况时间复杂度。
均摊时间复杂度就是一种特殊的平均时间复杂度。

小结：引入最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度这几个概念是因为同一段代码在不同输入情况下，复杂度量级有可能不一样，通过比较分析，我们可以更加全面地表示一段代码的执行效率。

思考题一：有人说，我们项目之前都会进行性能测试，再做代码的时间复杂度、空间复杂度分析，是不是多此一举呢？而且，每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？你怎么看待这个问题呢？

参考回答：

1.复杂度分析是一个理论分析，与宿主无关，能让程序员在写代码时对算法的执行效率有个大致认识，从而写出效率更高的程序；
2.通过练习就能达到熟练地看出是否浪费时间，比如复杂度越低阶效率越高，为代码质量考虑并不算浪费时间。

思考题二：分析下面这个 add() 函数的时间复杂度。

// 全局变量，大小为 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;
}