复杂度分析

发表于 | 分类于
字数统计: 14k

我们知道，数据结构和算法本身解决的是『快』和『省』的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢？这就是我们今天要介绍的内容：时间、空间复杂度分析。

为什么需要复杂度分析？

你可能会有些疑惑，我直接把代码跑一遍不就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？这种分析能比我实际跑一遍得到的数据更准确吗？

首先，我可以肯定地说，你这种评估方法是没有任何问题的。很多数据结构和算法书籍还给它起了一个名字，叫事后统计法。但是，事后统计法有着非常大的局限性。

  • 测试结果非常依赖测试环境
    • 测试环境中硬件的差异会对测试结果造成很大的影响。比如，同样一段代码，分别用 Intel Core i9 处理器和 Intel Core i3 处理器来运行，那 i9 处理器肯定要比 i3 处理器更快处理完。还有，比如原本在这台机器上 a 代码执行的速度比 b 代码要快，等我们换到另一台机器上时，可能会有相反的结果。
  • 测试结果受数据规模的影响
    • 对于排序算法来说，如果测试数据规模太小，测试结果可能无法真实地反应算法的性能。比如，对于小规模的数据排序，插入排序可能比快速排序更快！

所以，我们需要一个不用执行代码，就可以粗略地估计算法的执行效率的方法。也就是时间、空间复杂度分析方法。

大 O 复杂度表示法

算法的执行效率，粗略地讲，就是算法代码的执行时间。但如何才能在不运行代码的情况下，用『肉眼』得到一段代码的执行时间呢？

示例 1

这里有段示例代码，求 1~n 的和。现在，我们来估算一下这段代码的执行时间。

1
2
3
4
5
6
7
8
int cal_1(int n) {
    int sum = 0;
    int i = 1;
    for (; i <= n; ++i) {
        sum = sum + i;
    }
    return sum;
}

从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码 CPU 执行的次数、时间都不一样，但是，我们这里只是粗略估计，可以假设每行代码执行的时间都一样，为一个 \(unitTime\)。在这个假设的基础上，这段代码的总执行时间是多少呢？

第 2、3 行代码分别需要 1 个 \(unitTime\) 的执行时间，第 4、5 行都运行了 n 遍，所以需要 \( 2n \ast unitTime \) 的执行时间，所以这段代码总的执行时间就是 \((2n+2)\ast unitTime\)。

示例 2

按照这个分析思路，我们再来看这段代码。

1
2
3
4
5
6
7
8
9
10
11
12
int cal_2(int n) {
    int sum = 0;
    int i = 1;
    int j = 1;
    for (; i <= n; ++i) {
        j = 1;
        for (; j <= n; ++j) {
            sum = sum + i * j;
        }
    }
    return sum;
}

第 2、3、4 行代码，每行都需要 1 个 \(unitTime\) 的执行时间，第 5、6 行代码循环执行了 n 遍，需要 \(2n \ast unitTime\) 的执行时间，第 7、8 行代码循环执行了 \(n^2\) 遍，所以需要 \(2n^2 \ast unitTime\) 的执行时间。所以，整段代码的执行时间 \(T(n) = (2n^2+2n+3)\ast unitTime\)。

由此，我们可以得出一个结论，代码的执行时间 \(T(n)\) 与代码的执行次数成正比。用公式来表示的话，如下所示

$$ T(n)=O(f(n)) $$

公式中的 \(T(n)\) 我们已经讲过了，它表示代码执行的时间；其中 \(n\) 表示数据的规模；\(f(n)\) 表示代码执行的次数。公式中的 \(O\)，表示代码的执行时间 \(T(n)\) 与 \(f(n)\) 成正比。

小结

所以，第一个例子中的 \(T(n) = O(2n+2)\)，第二个例子中的 \(T(n) = O(2n^2+2n+3)\)。这就是大 \(O\) 时间复杂度表示法。大 \(O\) 时间复杂度实际上并不代表代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

当 n 趋近于无穷大时，公式中的常量、低阶项和首项系数并不左右增长趋势，所以都可以忽略。我们只需要记录一个最高阶的量级就可以了。如果用大 \(O\) 表示法来表示刚才讲的那两段代码的时间复杂度，就可以记为：\(T(n) = O(n)\)， \(T(n) = O(n^2)\)。

时间复杂度分析

前面介绍了大 \(O\) 时间复杂度的由来和表示方法。下面介绍两个比较实用的分析时间复杂度的方法。

最大法则

总复杂度等于量级最大的那段代码的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int cal_3(int n) {
    int sum_1 = 0;
    int p = 1;
    for (; p < 100; ++p) {
        sum_1 = sum_1 + p;
    }
    int sum_2 = 0;
    int q = 1;
    for (; q < n; ++q) {
        sum_2 = sum_2 + q;
    }
    int sum_3 = 0;
    int i = 1;
    int j = 1;
    for (; i <= n; ++i) {
        j = 1;
        for (; j <= n; ++j) {
            sum_3 = sum_3 + i * j;
        }
    }
    return sum_1 + sum_2 + sum_3;
}

这个代码分为三部分，分别是求 sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的作为整段代码的复杂度。

第一段的时间复杂度是多少呢？这段代码循环执行了 100 次，所以是一个常量的执行时间，跟 \(n\) 的规模无关。

这里要强调一下，即便这段代码循环 10000 次、100000 次，只要是一个已知的数，跟 n 无关，照样也是常量级的执行时间。当 n 趋向于无限大的时候，就可以忽略。尽管对代码的执行时间会有很大影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，我们都可以忽略掉。因为它并不影响增长趋势。

那第二段代码和第三段代码的时间复杂度是多少呢？答案是 \(O(n)\) 和 \(O(n^2)\)。

综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为 \(O(n^2)\)。

乘法法则

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int cal(int n) {
    int ret = 0;
    int i = 1;
    for (; i < n; ++i) {
        ret = ret + f(i);
    }
    return ret;
}

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

我们单独看 cal() 函数。假设 f() 只是一个普通的操作，那第 4～6 行的时间复杂度就是，\(T_1(n) = O(n)\)。但 f() 函数本身不是一个简单的操作，它的时间复杂度是 \(T_2(n) = O(n)\)，所以，整个 cal() 函数的时间复杂度就是，\(T(n) = T_1(n) \times T_2(n) = O(n \times n) = O(n^2)\)。

常见复杂度

\(O(1)\)

首先你必须明确一个概念，\(O(1)\) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 \(O(1）\)，而不是 \(O(3)\)。

1
2
3
int i = 8; 
int j = 6; 
int sum = i + j;

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

\(O(\log n)\)

对数阶时间复杂度十分常见，同时也是最难分析的一种时间复杂度。我们通过一个例子来说明一下。

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

根据我们前面讲的复杂度分析方法，第三行代码是循环执行次数最多的。所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2，当大于 n 时，循环结束。即

$$ 2^x=n $$

所以，只要解出来 x，就知道这行代码的执行次数了。而 \(x=\log_2 n\)，所以，这段代码的时间复杂度就是 \(O(\log_2 n)\) 。

现在，我们把代码稍微改下，下面这段代码的时间复杂度是多少？

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

根据刚刚讲的思路，很容易就能看出来，这段代码的时间复杂度为 \(O(\log_3 n)\)。

**实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 \(O(\log n)\)**。为什么呢？

我们知道，对数之间是可以相互转换的，\(\log_3 n\) 就等于 \(\log_3 2 \times \log_2 n\)，所以 \(O(\log_3 n) = O(C \times \log_2 n)\)，其中 \(C=\log_3 2\)，是一个常量。基于我们前面的分析：**在采用大 \(O\) 表示复杂度的时候，可以忽略系数，即 \(O(C\times f(n)) = O(f(n))\)**。所以，\(O(\log_2 n)\) 就等于 \(O(\log_3 n)\)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的底，统一表示为 \(O(\log n)\)。

\(O(n\log n)\)

如果你理解了 \(O(\log n)\)，那 \(O(n \log n)\) 就很容易理解了。还记得我们讲的乘法法则吗？如果一段代码的时间复杂度是 \(O(\log n)\)，我们循环执行 \(n\) 遍，时间复杂度就是 \(O(n \log n)\) 了。\(O(n \log n)\) 也是一种常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 \(O(n \log n)\)。

空间复杂度分析

前面，咱们花了很大的篇幅讲大 \(O\) 表示法和时间复杂度分析，理解了前面讲的内容，空间复杂度分析介绍起来就非常简单了。

前面讲过，时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

1
2
3
4
5
6
7
8
9
10
11
void print(int n) {
    int i = 0;
    int[] a = new int[n];
    for (; i < n; ++i) {
        a[i] = i * i;
    }

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

跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 \(n\) 没有关系，所以可以忽略。第 3 行申请了一个大小为 \(n\) 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 \(O(n)\)。

我们常见的空间复杂度就是 \(O(1)\)、\(O(n)\)、\(O(n^2)\)，像 \(O(\log n)\)、\(O(n \log n)\) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握上面的这些内容已经足够了。

小结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶依次为：\(O(1)\)、\(O(\log n)\)、\(O(n)\)、\(O(n \log n)\)、\(O(n^2)\)。几乎所有的数据结构和算法的复杂度都跑不出这几个。

其实，只要提到数据结构与算法，就一定离不开时间、空间复杂度分析。而且，我个人认为，复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。

几种常见的时间复杂度

引用