系列文章请查看 「数据结构&算法」必知必会系列：1. 开篇#计划路线
承接上篇请查看 「数据结构&算法」必知必会系列：2. 时间 & 空间复杂度（上）
时间复杂度分析
常量执行复杂度为 O(1)
在讲套路之前，先说一个原则：常量执行复杂度永远是 O(1)
理解这个原则，先来看一个 🌰 （golang 实现，应该不难读）
for a := 0; a < 100000; a++ {
for b := 0; b < a; b++ {
fmt.Printf("%d ", b)
}
}
https://play.golang.org/p/itly0TWKUPe ，你会发现提示 timeout running program
那这个复杂度是多少（大O表示）？🙌 O(1)
即使改为更大，1000000000… 只要是常量，就都可以忽略，尽管实际执行时间会有很大影响。
但是「时间复杂度」表示的是执行效率与数据规模增长的变化趋势，所以不管常量多大，都可以忽略。
实用的分析套路
好了，开始套路，举第一个 🌰
func calcSum(n int) int {
sum_1, sum_2, sum_3 := 0, 0, 0
for p := 0; p <= 100000; p++ {
sum_1 = sum_1 + p
}
for q := 0; q < n; q++ {
sum_2 = sum_2 + q
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
sum_3 = sum_3 + i*j
}
}
return sum_1 + sum_2 + sum_3
}
先不看代码实现，你观察到了什么？或者说形态是啥？
🙌 两个循环 + 一个嵌套循环
很好，我们继续分开看：循环1常量；循环2是 O(n)；循环3嵌套，也不难看出，是 O(n²) ；
简单加一下，复杂度 = O(1) + O(n) + O(n²)
如果觉得以上分析仍有难度，请回炉 上篇
https://play.golang.org/p/e4Uaka1ZeTu 可 Go Play一下
当 n 趋于 ∞ 时，整体复杂度仅与大量级 n² 相关，故，整体的复杂度 = O(n²)
虽然，是个很简单的🌰 但是，我们可得出如下套路：
- 只需关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积（可以把乘法法则看成是嵌套循环）
本文 🌰 还是比较简单的，实际代码会有函数和递归等，继续总结步骤如下：
- 先去干扰项（常数、量极小的忽略）
- 从内向外分析，从最深层开始分析
- 如果遇到函数调用，深入函数分析
可能，还是觉得有点糊糊的。没事，继续看下去，多看算法案例、多分析。对套路和步骤就有「感觉」了。
常见时间复杂度
下面将举几个具体的常见时间复杂度量级以及对应的🌰分析
虽然，代码千差万别（不同语言实现不同人写出的真·千奇百怪），但常见的复杂度量级并不多，先上总结
除去多个数量级（m、n），可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2^n) 和 O(n!)
O(m+n) O(m*n)
算法的代码复杂度分析，通常只引入一个数据规模，但也有可能会引入两个数据规模 （多个不在常用讨论中）
直接上 🌰
func calcSum(n int, m int) int {
sum_1, sum_2 := 0, 0
for i := 0; i < n; i++ {
sum_1 = sum_1 + i
}
for i := 0; i < m; i++ {
sum_2 = sum_2 + i
}
return sum_1 + sum_2
}
n、m 是两个数据规模，故整体复杂度 = O(m+n)
https://play.golang.org/p/1P1n3q75ET8 可 Go Play一下
乘法的话，再上个 🌰 ，如下：
func calcSum(n int, m int) int {
sum := 0
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
sum = sum + i*j
}
}
return sum
}
这边🤚乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
故，复杂度 = O(m*n)
https://play.golang.org/p/VoZcACv3Box 可 Go Play一下
O(1)
再度明确一个概念，O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。
一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
&& 再度强调 =》常量执行复杂度永远是 O(1)
O(logn)、O(nlogn)
对数阶时间复杂度非常常见，比起其他的，相对最难分析。
继续，举个 🌰，代码比较简单（这里面的 for 为 go 的省略写法，可理解为 while）
func calc(n int) int {
i := 1
for i <= n {
i = i * 2
}
return i
}
这边，需要用到套路一：关注循环执行次数最多的一段代码 i = i*2
个人分析方式（有点🐷），先列一下 i 循环的值具体会是什么，如下：
1, 2, 4, 8, 16, 32 ... 2^x
可得知，直到 2^x <= n 🔚 ，求循环次数其实是解个数学方程式了，如下：
基于之前的理论：在采用大 O 标记复杂度的时候，可以忽略系数。我们忽略对数的“底”，统一表示为 O(logn)
那 O(nlogn) 呢？🙌 乘法法则
如果一段代码的时间复杂度是 O(logn)，循环执行 n 遍，时间复杂度就是 O(nlogn) 了。
O(nlogn) 也是一种常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。
O(n²)
🙌 乘法法则，不多说了吧，嵌套循环；其实也有三次方的，不常见这里就不提了。
复杂度比较
直接上图
O(2^n) 和 O(n!)
前面提到，常见非多项式量级只有两个：O(2^n) 和 O(n!)。
当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。
所以，非多项式时间复杂度的算法其实是非常低效的算法，这里就不介绍了。
主定理公式
数学好的👦，可以考虑用「主定理公式」（尤其是复杂的递归分析）
个人表示看不懂。。。 有兴趣的参见 算法导论：用主定理求解递归式 计算算法复杂度
个人体会
(*´▽｀)ノノ 嗯，简单说下个人对复杂度分析的体会，就是两字：「感觉」
有些算法高手或者 LeetCode 刷得多了，简单的一眼就能看出其复杂度，respect~
引一段专栏作者（王争大佬）的感悟：
复杂度分析并不难，关键在于多练。 之后讲后面的内容时，我还会带你详细地分析每一种数据结构和算法的时间、空间复杂度。只要跟着我的思路学习、练习，你很快就能和我一样，每次看到代码的时候，简单的一眼就能看出其复杂度，难的稍微分析一下就能得出答案。
信了大佬，立个 Flag，坚持学习完 各种常见算法 & 切切实实练习之后的每个 🌰