作者：京东物流 崔旭
咱们都晓得，数据结构和算法自身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个十分重要的考量指标。那如何来掂量你编写的算法代码的执行效率呢？这里就要用到咱们明天要讲的内容：工夫、空间复杂度剖析。
1 为什么须要复杂度剖析？
你可能会有些纳闷，我把代码跑一遍，通过统计、监控，就能失去算法执行的工夫和占用的内存大小。为什么还要做工夫、空间复杂度剖析呢？这种分析方法能比实实在在跑一遍失去的数据更精确吗？
首先能够必定地说，这种评估算法执行效率的办法是正确的。很多数据结构和算法书籍还给这种办法起了一个名字，叫预先统计法。然而，这种统计办法有十分大的局限性。
1.1 测试后果十分依赖测试环境
测试环境中硬件的不同会对测试后果有很大的影响。比方，咱们拿同样一段代码，别离用 Intel Core i9 处理器和 Intel Core i3 处理器来运行，i9 处理器要比 i3 处理器执行的速度快很多。还有，比方本来在这台机器上 a 代码执行的速度比 b 代码要快，等咱们换到另一台机器上时，可能会有截然相同的后果。
1.2 测试后果受数据规模的影响很大
对同一个排序算法，待排序数据的有序度不一样，排序的执行工夫就会有很大的差异。极其状况下，如果数据曾经是有序的，那排序算法不须要做任何操作，执行工夫就会十分短。除此之外，如果测试数据规模太小，测试后果可能无奈实在地反馈算法的性能。比方，对于小规模的数据排序，插入排序可能反倒会比疾速排序要快！
所以，咱们须要一个不必具体的测试数据来测试，就能够粗略地预计算法的执行效率的办法，这就是咱们接下来要说的大 O 复杂度表示法。
2 大 O 复杂度表示法
算法的执行效率，粗略地讲，就是算法代码执行的工夫。然而，如何在不运行代码的状况下，用“肉眼”失去一段代码的执行工夫呢？
这里有段非常简单的代码，求 1,2,3…n 的累加和。当初，一块来估算一下这段代码的执行工夫吧。
从 CPU 的角度来看，这段代码的每一行都执行着相似的操作：读数据 - 运算 - 写数据。只管每行代码对应的 CPU 执行的个数、执行的工夫都不一样，然而，咱们这里只是粗略预计，所以能够假如每行代码执行的工夫都一样，为 unit_time。在这个假如的根底之上，这段代码的总执行工夫是多少呢？
第 2、3 行代码别离须要 1 个 unit\_time 的执行工夫，第 4、5 行都运行了 n 遍，所以须要 2n\_unit\_time 的执行工夫，所以这段代码总的执行工夫就是 (2n+2)\_unit_time。能够看进去，所有代码的执行工夫 T(n) 与每行代码的执行次数成正比。
依照这个剖析思路，咱们再来看这段代码。
咱们仍旧假如每个语句的执行工夫是 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) = (2n²+2n+3)。这就是大 O 工夫复杂度表示法。大 O 工夫复杂度实际上并不具体示意代码真正的执行工夫，而是示意代码执行工夫随数据规模增长的变化趋势，所以，也叫作渐进工夫复杂度，简称工夫复杂度。
当 n 很大时，你能够把它设想成 10000、100000。而公式中的低阶、常量、系数三局部并不左右增长趋势，所以都能够疏忽。咱们只须要记录一个最大量级就能够了，如果用大 O 表示法示意刚讲的那两段代码的工夫复杂度，就能够记为：T(n) = O(n)；T(n) = O(n²)。
3 工夫复杂度剖析
后面介绍了大 O 工夫复杂度的由来和示意办法。当初咱们来看下，如何剖析一段代码的工夫复杂度？
3.1 只关注循环执行次数最多的一段代码
大 O 这种复杂度示意办法只是示意一种变化趋势。咱们通常会疏忽掉公式中的常量、低阶、系数，只须要记录一个最大阶的量级就能够了。所以，咱们在剖析一个算法、一段代码的工夫复杂度的时候，也只关注循环执行次数最多的那一段代码就能够了。这段外围代码执行次数的 n 的量级，就是整段要剖析代码的工夫复杂度。
为了便于你了解，我还拿后面的例子来阐明。
其中第 2、3 行代码都是常量级的执行工夫，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4、5 行代码，所以这块代码要重点剖析。后面咱们也讲过，这两行代码被执行了 n 次，所以总的工夫复杂度就是 O(n)。
3.2 加法法令：总复杂度等于量级最大的那段代码的复杂度
这里还有一段代码。
这个代码分为三局部，别离是求 sum\_1、sum\_2、sum_3。咱们能够别离剖析每一部分的工夫复杂度，而后把它们放到一块儿，再取一个量级最大的作为整段代码的复杂度。
第一段的工夫复杂度是多少呢？这段代码循环执行了 100 次，所以是一个常量的执行工夫，跟 n 的规模无关。
即使这段代码循环 10000 次、100000 次，只有是一个已知的数，跟 n 无关，照样也是常量级的执行工夫。当 n 无限大的时候，就能够疏忽。只管对代码的执行工夫会有很大影响，然而回到工夫复杂度的概念来说，它示意的是一个算法执行效率与数据规模增长的变化趋势，所以不论常量的执行工夫多大，咱们都能够疏忽掉。因为它自身对增长趋势并没有影响。
那第二段代码和第三段代码的工夫复杂度是多少呢？答案是 O(n) 和 O(n²)。
综合这三段代码的工夫复杂度，咱们取其中最大的量级。所以，整段代码的工夫复杂度就为 O(n²)。也就是说：总的工夫复杂度就等于量级最大的那段代码的工夫复杂度。那咱们将这个法则形象成公式就是：
如果 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.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³)。落实到具体的代码上，咱们能够把乘法法令看成是嵌套循环，我举个例子给你解释一下。
咱们独自看 cal() 函数。假如 f() 只是一个一般的操作，那第 4～6 行的工夫复杂度就是，T1(n) = O(n)。但 f() 函数自身不是一个简略的操作，它的工夫复杂度是 T2(n) = O(n)，所以，整个 cal() 函数的工夫复杂度就是，T(n) = T1(n)\_T2(n) = O(n\_n) = O(n²)。
3.4 几种常见工夫复杂度实例剖析
尽管代码千差万别，然而常见的复杂度量级并不多。略微总结了一下，这些复杂度量级简直涵盖了大部分的场景。
- 常量阶 O(1)
- 对数阶 O(logn)
- 线性阶 O(n)
- 线性对数阶 O(nlogn)
- 平方阶 O(n²)
- 立方阶 O(n³) …
- 指数阶 O(2ⁿ)
- 阶乘阶 O(n!)
对于刚列举的复杂度量级，咱们能够粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2ⁿ) 和 O(n!)。
当数据规模 n 越来越大时，非多项式量级算法的执行工夫会急剧减少，求解问题的执行工夫会有限增长。所以，非多项式工夫复杂度的算法其实是十分低效的算法。咱们次要来看几种常见的多项式工夫复杂度。
1.O(1)
首先你必须明确一个概念，O(1) 只是常量级工夫复杂度的一种示意办法，并不是指只执行了一行代码。比方这段代码，即使有 3 行，它的工夫复杂度也是 O(1），而不是 O(3)。
只有代码的执行工夫不随 n 的增大而增长，这样代码的工夫复杂度咱们都记作 O(1)。或者说，个别状况下，只有算法中不存在循环语句、递归语句，即便有成千上万行的代码，其工夫复杂度也是 Ο(1)。
2.O(logn)、O(nlogn)
对数阶工夫复杂度十分常见，同时也是最难剖析的一种工夫复杂度。我通过一个例子来阐明一下。
依据咱们后面讲的复杂度分析方法，第三行代码是循环执行次数最多的。所以，咱们只有能计算出这行代码被执行了多少次，就能晓得整段代码的工夫复杂度。
从代码中能够看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环完结。
实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：
所以，咱们只有晓得 x 值是多少，就晓得这行代码执行的次数了。通过 2ˣ=n 求解 x，x=log₂n，所以，这段代码的工夫复杂度就是 O(log₂n)。
当初，我把代码略微改下，你再看看，这段代码的工夫复杂度是多少？
依据我刚刚讲的思路，很简略就能看进去，这段代码的工夫复杂度为 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(logn)，那 O(nlogn) 就很容易了解了。还记得咱们刚讲的乘法法令吗？如果一段代码的工夫复杂度是 O(logn)，咱们循环执行 n 遍，工夫复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种十分常见的算法工夫复杂度。比方，归并排序、疾速排序的工夫复杂度都是 O(nlogn)。
3.O(m+n)、O(m*n)
咱们再来讲一种跟后面都不一样的工夫复杂度，代码的复杂度由两个数据的规模来决定。老规矩，先看代码！
从代码中能够看出，m 和 n 是示意两个数据规模。咱们无奈当时评估 m 和 n 谁的量级大，所以咱们在示意复杂度的时候，就不能简略地利用加法法令，省略掉其中一个。所以，下面代码的工夫复杂度就是 O(m+n)。
针对这种状况，原来的加法法令就不正确了，咱们须要将加法规定改为：T1(m) + T2(n) = O(f(m) + g(n))。然而乘法法令持续无效：T1(m)\_T2(n) = O(f(m)\_f(n))。
4 空间复杂度剖析
后面，咱们花了很长时间讲大 O 表示法和工夫复杂度剖析，了解了后面讲的内容，空间复杂度剖析方法学起来就非常简单了。
工夫复杂度的全称是渐进工夫复杂度，示意算法的执行工夫与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度，示意算法的存储空间与数据规模之间的增长关系。
还是拿具体的例子来阐明。
跟工夫复杂度剖析一样，咱们能够看到，第 2 行代码中，咱们申请了一个空间存储变量 i，然而它是常量阶的，跟数据规模 n 没有关系，所以咱们能够疏忽。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。
咱们常见的空间复杂度就是 O(1)、O(n)、O(n²)，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度剖析比工夫复杂度剖析要简略很多。
5 内容小结
复杂度也叫渐进复杂度，包含工夫复杂度和空间复杂度，用来剖析算法执行效率与数据规模之间的增长关系，能够粗略地示意，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)。