系列文章请查看 「数据结构&算法」必知必会系列：1. 开篇#计划路线
承接上篇请查看 「数据结构&算法」必知必会系列：3. 时间 & 空间复杂度（下）
最好、最坏情况时间复杂度
直接上 🌰 （golang 实现，应该不难读）
func find(arr []int, x int) int {
pos := -1
for i := 0; i < len(arr); i++ {
if arr[i] == x {
pos = i
}
}
return pos
}
看不懂也没关系，这段代码实现功能（暂不考虑数值边界）：在一个无序的数组（arr）中，查找变量 x 出现的位置，如果没有找到，就返回 -1
复杂度为多少？🙌 O(n)
P.S 其中，n 代表数组的长度，即 len(arr)；若有疑问，可回炉上一篇博文 3. 时间 & 空间复杂度（下）
但是，在数组中查找一个数据，并不需要每次都把整个数组都遍历一遍，因为有可能中途找到就提前结束循环了。
上面的代码可以优化一下，如下：
func find(arr []int, x int) int {
pos := -1
for i := 0; i < len(arr); i++ {
if arr[i] == x {
pos = i
break
}
}
return pos
}
那么，问题来了，优化过后（加了 break），代码的时间复杂度还是 O(n) 吗？
上一篇讲的分析方法，还能解决这个问题么？
🙌 不能了 …
于是，继续引入三个概念：最好（情况）时间复杂度、最坏（情况）时间复杂度和平均（情况）时间复杂度。
这里，先来看「最好、最坏时间复杂度」，上述 🌰 还是比较好分析的
- 最好 =》一次就找到，即 O(1)
- 最坏 =》最后才找到或者没找到，即 O(n)
可参考 https://play.golang.org/p/zYTQRcx9i9h（增加了打印信息），返回示例结果见图 ↓：
通常情况下，最好、最坏情况下的时间复杂度分析起来还是比较简单的。
平均情况时间复杂度
平均，其实是统计学术语，表示一组数据集中趋势的量数。如果需要分析上述 🌰 的平均情况时间复杂度，还需要加入概率的计算，继续 🐷 方式，一个一个值来：
比如，已知 arr=[]int{1,2,3,4,5, ..., n}
我们先假设找到的概率是 1/2
找 1 =》循环 1 次，概率为 (1/n)*(1/2)
找 2 =》循环 2 次，概率为 (1/n)*(1/2)
... ...
找 n => 循环 n 次，概率为 (1/n)*(1/2)
找不到 => 循环 n， 概率 1/2
去掉系数和常量，这段代码的加权平均时间复杂度仍然是 O(n)
实际上，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况，使用一个复杂度就可以满足需求了（比如上一篇博文的示例）。只有不同输入情况下，复杂度有量级区分，才会区分。
均摊时间复杂度
👇 引入一个更加高级的概念，均摊时间复杂度，以及它对应的分析方法，摊还分析（或者叫平摊分析）。
均摊，和平均有啥差？（不想学了 … ）
先醒醒，看下面 🌰
func insert(oArr []int, count int, new int) (nArr []int) {
if len(oArr) < count {
nArr = append(oArr, new)
} else {
sum := 0
for i := 0; i < len(oArr); i++ {
sum = sum + oArr[i]
}
nArr = []int{sum, new}
}
return
}
看不懂没关系，解释一下实现：往数组中插入数据
- 未满（len(oArr) < count），直接将数据插入数组
- 满了（len(oArr) = count），for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入
注意！输入 count 仅可能小于 Arr 长度 或者等于其长度。
仅供举例，实际上没人会这么写 … 可参考 https://play.golang.org/p/pYU1Tmvk5o6
显然，不同输入（count）情况下，复杂度有量级区分，先分析下「最好&最坏」：
🙌 最好 O(1) 最坏 O(n)
平均的分析相对复杂一点，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，即 O(n)。那么，整体的「平均复杂度」为：
列式分析真的好麻烦鸭！！脑壳疼。。。
其实，凭「感觉」，完全不用列式，还是上面那个 🌰。思考一下，只有一种情况是 O(n)，那么，根据“平均”的定义——数据集中趋势的量数 来看，这一种情况完全可以忽略嘛。直接得出 O(1) 简单粗暴。
所以，针对这样一种特殊场景的复杂度分析，我们并不需要像之前讲平均复杂度分析方法那样，找出所有的输入情况及相应的发生概率，然后再计算加权平均值。
针对这种特殊的场景，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度我们起了一个名字，叫均摊时间复杂度。
在能够应用均摊时间复杂度分析的场合，一般 均摊时间复杂度就等于最好情况时间复杂度。
均摊时间复杂度就等于最好情况时间复杂度
均摊时间复杂度就等于最好情况时间复杂度
（重要的事儿说三遍，上面分析你也可以忘了，<(￣▽￣)/ ）
尽管很多数据结构和算法书籍都花了很大力气来区分平均时间复杂度和均摊时间复杂度，但其实我个人认为，均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多精力去区分它们。
总结
不同输入情况下，若复杂度有量级区分，会分析其 最好、最坏情况时间复杂度，以及 平均情况时间复杂度。
均摊时间复杂度，是一种特殊的平均时间复杂度，一般情况，均摊时间复杂度就等于最好情况时间复杂度。
在引入这几个概念之后，我们可以更加全面地表示一段代码的执行效率。