数据结构与算法 - 复杂度分析

学习算法是为了更快、更节省内存的解决问题，那么如何判断定一个算法是不是足够快、足够省内存，这就需要复杂度分析。复杂度分析包括时间复杂度分析和空间复杂度分析。

复杂度分析能力之于开发者，就像审美能力之于设计师，因此，其重要性是不言而喻的。说道这里，可能会想到，我们平时常用的测试性能的方法，直接把算法跑一遍，然后直接可以知道算法跑的快慢了，为什么还要费劲去分析呢？首先可以肯定的说，这两种方法都有不同的应用场景，比如很多刷题平台，测试算法快慢就是这种方法，并且该方法还有一个名字，叫做事后统计法。但是，这种方法存在一定的局限性，主要有两方面：

测试结果与运行环境相关。同样的算法在不同的计算机上，运行的速度不一样。
测试结果与数据规模相关。同样一个排序算法，排列100个元素，和排列100万个元素用时肯定不同。

所以就需要一种不用进行数据输入，就能够知道算法快慢的方法，这就是复杂度分析方法。这里需要注意的是，复杂度分析只是粗略的估计算法的执行效率，对于特定的数据规模，复杂度低的不一定比复杂度高的执行速度快，如果现在还不能理解这句话，没关系，等看完本文之后再来理解。

$O(n)$表示法

首先考虑一个问题，如果给定一段代码，来计算它的执行时间，如何来进行计算？很简单，把每一条语句的执行时间求和就可以了嘛，看下面一段代码。

int cal(int n){
    int sum = 0;
    for(int i=0;i<n;++i){
        sum += i;
    }
    return sum;
}

计算过程如下：

首先假设每一条语句执行时间相同，都为单位时间$t$
第2行执行1次，时间为：$1t$
第3行执行n次，时间为：$nt$
第4行执行n次，时间为：$nt$
第6行执行1次，时间为：$1t$
总计时间为：$T_1(n)=(1+n+n+1)t=(2n+2)t$

到此为止，我们已经估算出来上面代码时间了，时间与输入的 n 有关，关系如下图：

再看一个稍微复杂点的：

int cal(int n){
    int sum = 0;
    for(int i = 0;i<n;++i){
        int j = 0;
        for(;j<n;++j){
            sum += i*j;
        }
    }
    return sum;
}

还是根据上面的步骤，计算时间复杂度：

首先假设每一条语句的执行时间相同，都为单位时间$t$
第2行执行1次，时间为：$1t$
第3行执行n次，时间为：$nt$
第4行执行n次，时间为：$nt$
第5行为嵌套循环，执行$n*n$次，时间为$n^2t$
第6行在内层循环体内，执行次数是$n*n$，时间为$n^2t$
第9行执行1次，时间为:$1t$
总计时间为：$T_2(n)=(1+n+n+n^2+n^2+1)t=(2n^2+2n+2)t$

可以看出来，最终的时间依旧跟 n 有关，关系如下图：

通过上面例子可以看到，每次我们都假设，每一条语句的执行时间是相同的，即我们并不关心每一条语句执行需要多少时间，而只关注它与单位时间的函数关系，所以我们可以用另一种形式来写上面的表达式：

$\begin{aligned} T_1(n) &= (2n+2)t\\ &= O(2n+2)\\ T_2(n) &= (2n^2+2n+2)t\\ &= O(2n^2+2n+2) \end{aligned}$

这就是大 O 时间复杂度表示法，它表示算法执行时间，在数据规模 n 发生变化时的变化趋势，因此，也叫渐进时间复杂度，简称时间复杂度。

因为关注的重心在于变化趋势（函数图形形状），而公式中的低阶、常量、系数部分对趋势影响较小，所以都可以忽略。因此上面的两个表达式就成了：

$\begin{aligned} T_1(n) &= O(2n+2)\\ &= O(n)\\ T_2(n) &= O(2n^2+2n+2)\\ &= O(n^2) \end{aligned}$

通过下图可以看到，两者之间的趋势是一致的。

几个小技巧

通过上面例子，可能会发现以下几个计算复杂度的规律：

最大值法则：最终结果只与复杂度最高的（循环次数最多）的代码有关。（因为低阶对于趋势的影响较小，所以忽略）
乘法法则：嵌套代码的复杂度 = 本身复杂度 x 外层循环复杂度。比如第二个例子中的第5、6行，它们的复杂度 = 本身复杂度 x 外层循环复杂度 = n x n。

几种常见的复杂度

复杂度	表示
常数阶	$O(1)$
对数阶	$O(\log{n})$
线性阶	$O(n)$
线性对数阶	$O(n\log{n})$
K方阶	$O(n^2)$,$O(n^3)$,$O(n^k)$
指数阶	$O(2^n)$
阶乘阶	$O(n!)$

通过下图，可以直观的看到它们的趋势。

常数阶$O(1)$

首先看下面一段代码：

1
2
3

int i = 2;
int j = 5;
int k = i + j;

很简单吧，这段代码一共执行了3条语句，那么复杂度为3，那么用大 O 表示呢？$T(n) = O(3)$，看上去没什么问题，但是如果代码有5行、10行、10万行呢？难道还写成$O(5)$、$O(10)$、$O(100000)$？看上去不好看，所以对于不随着数据规模变化的复杂度（表达式里面没有n），统统都用$O(1)$表示。

对数阶$O(\log{n})$

对数阶时间复杂度非常常见，并且非常高效。但是复杂度最难分析，这是因为它并不像其他复杂度，可以通过相乘、相加来得到，它往往需要我们先总结规律，然后找出指数形式，最后再求对数。

先看下面一个例子：

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

根据上面提到的最大值法则，我们只需要计算循环部分的复杂度，那么就需要计算到底循环了多少次，下面是计算步骤：

假设循环停止时，执行了 k 次，接下来就变成了求 k 的问题。
我们有哪些已知条件呢？
- 当执行 k 次后，循环停止，即 i = n。
- 每执行 1 次，i 都乘以 2，执行 k 次后，$i = 2^k$
根据已知条件可得：$2^k=n$
最后求得： $k=\log_2{n}$

上面每次循环 i 都乘以2，如果乘以3、乘以5、乘以10000呢？最终的结果将是 $\log{3}{n}、\log{5}{n}、\log_{10000}{n}$。在使用大 O 表示法时，统统记做 $O(\log{n})$ 表示，这是为什么呢？

$\begin{aligned} T(n) = \log_{k}{n} = \log_{k}2*\log_2{n} \end{aligned}\tag{换底公式}$

其中$\log_{k}2$是与 n 无关的常量，所以在大 O 表示法中可以忽略，所以对数阶都可以表示为:$O(\log{n})$

理解了对数阶之后，再来看线性对数阶$O(n\log{n})$就很简单了，还记得上面提到的乘法法则吗？将对数阶$O(\log{n})$外面嵌套一个循环就成了线性对数阶。

int cal(int n){
    int sum = 0;
    for(int i = 0;i<n;++i){
        int j = 1;
        while(j <= n){
            j = j * 5;
        }
        sum = sum + j;
    }
    return sum;
}

可以按照上面的方法，自己计算一下，这段代码的复杂度。

多维输入

在之前的例子中，时间复杂度由数据规模 n 来决定，还有一些算法，它的数据输入包含多个维度，比如下面一个例子：

int cal(int m,int n){
    int sum_1 = 0;
    for(int i=0;i<m;++i){
        sum_1 = sum_1 + i;
    }

    int sum_2 = 0;
    for(int i=0;i<n;++i){
        sum_2 = sum_2 + i;
    }

    return sum_1 + sum_2;
}

在上面例子中，它的复杂度是有 m、n 来决定，并且都是线性复杂度，再来复习一下复杂度计算方法。

首先假设所有的运算时间相同，都为单位时间 $t$
第2行执行1次，时间为：$t$
第3、4行执行次数为 m 次，时间为： $mt$
第7行执行1次，时间为：$t$
第8、9行执行 n 次，时间为：$nt$
第12行执行1次，时间为：$t$
总和：$T(n)=(2m+2n+3)t$，利用大O表示法，省略低阶和单位时间：$T(n) = O(m+n)$

最好、最坏和平均

不知道你主要到没有，在上面所有的例子中，都没有出现 if 语句，所以每行代码的执行次数都是确定的，那么如果加入条件分支会怎么样呢？首先看下面一个例子。

// n 表示数组 array 的长度
int find(int[] array, int n, int x){
    int i = 0;
    int pos = -1;
    for (; i < n; ++i) {
        if (array[i] == x){
            pos = i;
            break;
        }
    }
    return pos;
}

这段代码的作用是从长度为n的数组array中，查找值为x的元素，找到之后立刻结束查找，下面分析一下这段代码的复杂度。

第 1、2 行复杂度：1
第 3 行执行多少次呢？如果不看循环体，那么它为 n，但是循环内执行了break，所以不能一概而论的认为是n了，这里就需要分情况讨论：
1. 最好的情况是，第一个元素就是要找的元素，此时复杂度为：1
2. 最坏的情况是，最后一个元素才找到元素，此时复杂度为：n
因此这里就引申出了最好情况复杂度、最坏情况复杂度，分别为$O(1)$、$O(n)$

最好和最坏都是极端的情况，出现的几率很小，而如何表示其他情况下的复杂度呢？这里引入了平均情况时间复杂度，我们先看下上面例子有几种查找结果，以及每种情况出现的概率：

可能情况	出现概率	复杂度
不在数组中	$1/2$	$T_1(n)=n$
出现在位置k	$1/2$	$T_2(n)=?$

出现或者不出现的概率相等，都为1/2。对于出现这种情况，数组的每个位置都有可能出现，因此每个位置出现的概率为(1/n)，因此每个位置的时间复杂度为：$k(1/n)$，（其中$k$为出现的位置），因此出现的总概率为：

$T_2(n)=\sum_{k=1}^{n}(k/n)$

平均情况时间复杂度为：

$\begin{aligned} T(n) &= \frac{T_1(n) + T_2(n)}{2}\\ &= \frac{n + {\sum_{k=1}^{n}(k/n)}}{2}\\ &= \frac{3n+1}{4} \end{aligned}$

大O表示法：

$T(n)=O({\frac{3n+1}{4}}) = O(n)$

摊还分析法

前面介绍了平均情况时间复杂度，这里再介绍一种特殊情况-均摊时间复杂度。先看一个例子，insert函数是将值val插入到数组array中，当数组满时，则将所有数据相加，然后把数据存到数组第一个位置，并且重置数组计数。

// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;

void insert(int val) {
    if (count == array.length) {
        int sum = 0;
        for (int i = 0; i < array.length; ++i) {
            sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
    }

    array[count] = val;
    ++count;
}

那么来分析一下这段代码的事件复杂度：

最好情况时间复杂度：当数组还有空闲空间时，直接设置数组元素即可，复杂度为$T(n) = 3t = O(1)$。
最坏情况时间复杂度：当数组满时，需要便利数组，复杂度$T(n) = (2n+6)t = O(n)$。
平均情况时间复杂度: 此时是多少呢，下面详细的分析一下。

可能情况	出现概率	复杂度
数组有空间(最好)	$P_1$	$T_1$
数组满元素(最坏)	$P_2$	$T_2$

上面列举了可能出现的两种情况，分别是最好情况、最坏情况。那么分别出现的概率是多少呢？换一种描述方法可能更加直观，数组 array 的长度为 n，当元素的个数为0-n-1时，此时数组有空间；当元素个数为 n 时，数组满元素。所以对于元素个数一共（n+1）种情况，对于每一种情况出现的概率都相同，所以：

$\begin{aligned} P_1 &= \frac{n}{n+1}\\ T_1 &= P_1 * 3t\\ &= (3 - \frac{3}{n+1})t\\ \\ P_2 &= \frac{1}{n+1}\\ T_2 &= P_2 * (2n+6)t\\ &= \frac{1}{n+1}*(2n+6)t\\ &= (2 + \frac{4}{n+1})t \end{aligned}$

最后，平均情况复杂度 $T(n) = T_1 + T_2 = (5 + \frac{1}{n+1})t = O(1)$。

同样是计算平均情况时间复杂度，为什么 find 的平均复杂度与最坏情况相同，而insert 的平均复杂度与最好情况相同？我们先对比一下这两函数有上面不同：

find 在极端情况下，复杂度才为O(1),insert在绝大部分情况，复杂度都为O(1)。
对于insert 函数，O(1) 和 O(n) 出现比较有规律，一个 O(n)后面接着 n-1 个O(1)。

对于 insert 这种情况的函数，在分析平均情况复杂度时，有一种更加简单的分析方法，叫做摊还分析法，其分析结果称作均摊时间复杂度。

那么如何使用摊还分析法呢？还是看上面的 insert 例子，首先已经知道，一个 O(n)后面跟着 n-1 个O(1)，可以将这些操作当作一个序列，将这个 O(n) 复杂度分摊到 n-1 个O(1)当中，分摊后整个序列的复杂度还是 O(1)，这就是摊还分析法的大致思路。

可以看出来，摊还分析法的使用限制很大，只有在少数特殊场景才会用到，所以这里只需要简单了解一下就好。另外，摊还分析法的分析结果叫做均摊时间复杂度，其实这里也没有必要咬文嚼字，大可以统一的认为就是平均时间复杂度。

空间复杂度

我们上面说了很多例子，基本都是时间复杂度分析的，主要用来描述算法的执行快慢，而现在介绍另一种复杂度分析 - 空间复杂度分析，空间复杂度关心的是内存空间的占用情况，所以在进行分析时，只需关注对象实例化语句，看下面一个例子。

void print(int n) {
    int i = 0;
    int[] a = new int[n];
    for (i; i <n; ++i) {
        a[i] = i * i;
    }

    for (i = n-1; i >= 0; --i) {
        print out a[i]
    }
}

空间复杂度分析步骤：

首先假设所有的类型（集合除外）占用的空间相同，都为单位空间 s
第2行分配1个对象，占用空间：s
第3行为一个数组，分配n个单位空间：ns
剩余代码都没有空间分配，因此为：0
总计：$S(n)=(1+n)s$,使用大O表示法：$S(n)=O(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)
最坏情况时间复杂度：O(n)
均摊时间复杂度：O(1)