复杂度分析

一、概念

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。应用于数学和计算机导论。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

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

二、为什么需要复杂度分析

预测算法所需要的资源
- 计算时间（CPU消耗）
- 内存空间（RAM消耗）
- 通信时间（带宽消耗）
预测算法的运行时间
- 在给定输入规模时，所执行的基本操作数量
- 或者称之为算法复杂度（Algorithm Complexity）
测试结果非常依赖测试环境
- 测试环境中硬件的不同对测试结果有很大的影响
测试结果受到数据规模的影响很大
- 对于小规模的数据排序，插入排序可能反倒会比快速排序要快

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

三、大 O 复杂度表示法

大O表示法就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。

一起来估算下面的代码执行时间，求1，2，3…n的累加和：

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

从CPU的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据 。尽管每行代码对应的CPU执行的个数、执行的时间都不一样，但是，这里只是粗略的估计，所以可以假设每行代码执行的时间都一样，为 unit_time。在这个假设基础之上，这段代码的总执行时间是多少呢？
第 2、3 行代码分别需要1个unit_time的执行时间，第 4、5 行都运行了n遍，所以需要2n * unit_time的执行时间，所以这段代码总的执行时间就是(2n + 2) * unit_time。可以看出来，所有代码的执行时间T(n)与每行代码的执行次数成正比。

按照这个分析思路，再来看下面这段代码

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

依旧假设每个语句的执行时间是unit_time。那这段代码的总执行时间T(n)是多少呢？
第 2、3、4 行代码，每行都需要 1 个 unit_time 执行时间，第 5、6 行代码循环执行了 n 遍，需要 2n * unit_time 的执行时间，第 7、8 行代码循环执行了 n² 遍，所以需要 2n² * unit_time 的执行时间。所以，整段代码总的执行时间 T(n) = (2n² + 2n + 3) * unit_time。

尽管不知道 unit_time 的具体值，但是通过上面两段代码的执行时间的推导过程，可以得到一个非常重要的规律，那就是：所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

这个规律总结成公式就是：

大O复杂度表示法

T(n) 表示代码执行的时间；
n 表示数据规模的大小；
f(n) 表示每行代码执行的次数总和（因为是一个公式，所以用f(n)来表示）；
O 表示代码的执行时间 T(n) 与 f(n) 表达式成正比；

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

当 n 很大时，比如10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚才的两段代码的时间复杂度，就可以记为: T(n) = O(n)；T(n) = O(n²)。

四、时间复杂度分析

1.只关注循环执行次数最多的一段代码

刚才说了，大 O 这种复杂度表示法只是表示一种变化趋势。通常会忽略掉公司中的常量、低价、系数，只需要记录一个最大阶量级就可以了，所有在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

如果T1(n) = O(f(n))，T2(n) = O(g(n))；那么T(n) = T1(n) + T2(n) = max(O(f(n)), O(g(n))) = O(max(f(n), g(n)))。

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

如果 T1(n) = O(f(n))，T2(n) = O(g(n))；那么 T(n) = T1(n)*T2(n) = O(f(n))*O(g(n)) = O(f(n)*g(n))。
也就是说，假设 T1(n) = O(n), T2(n) = O(n²)，则T1(n) * T2(n) = O(n³)。

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

虽然代码千差万别，但是常见的复杂度量级并不多。

复杂度量级

上面罗列的复杂度量级，可以粗略的分为两类，多项式量级和非多项式量级。其中非多项式量级只有两个：O(2ⁿ) 和 O(n!)。

当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以非多项式时间复杂度的算法其实是非常低效的算法。

1. O(1)

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

比如：下面代码即便有三行，它的时间复杂度也是O(1)，而不是O(3)。

1
2
3

int i = 1;
int j = 3;
int sum = i + j;

2. O(logn)、O(nlogn)

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

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

从代码中可以知道，变量 i 的取值就是一个等比数列。

等比数列

通过 2^x = n 求解 x 的公式 x = log₂n，所以这段代码的时间复杂度就是O(log₂n)。

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

根据刚才的思路，可以看出这段代码的时间复杂度为O(log₃n)
实际上不管是以 2 为底、以 3 为底还是以 10 为底，都可以把对数阶的时间复杂度记为 O(logn)。
我们知道，对数之间是可以相互转换的，log₃n 就等于 log₃2 * log₃n，所以O(log₃n) = O(C * log₂n)，其中 C * log₃2 是一个常量。基于在采用大 O 标记复杂度的时候可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log₂n) 就等于 O(log₃n)。因此，在对数阶时间复杂度的表示方法里，忽略对数的“底”，统一表示为 O(logn)。
O(nlogn)，如果一段代码的时间复杂度是 O(logn)，循环执行 n 遍，时间复杂度就变成 O(nlogn)了，而且 O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

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

再来看一种和前面不一样的时间复杂度，代码的复杂度由两个数据的规模来决定。

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

从上面代码中可以看出， m 和 n 是表示两个数据的规模。无法事先评估 m 和 n 谁的量级大，所以在表示时间复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是O(m+n)。

针对这种情况，原来的加法法则就不正确了，我们需要将加法法则改为:T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m) * T2(n) = O(f(m) * g(n))。

六、空间复杂度分析

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

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

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