【入门篇】复杂度分析（下） #3
Description
最后我们再讲几个个复杂度分析方面的知识点：
- 最好情况时间复杂度
- 最坏情况时间复杂度
- 平均情况时间复杂度
最好、最坏情况时间复杂度
话不多说，先看代码：
function find(array, x) {
let pos = -1;
for(let i = 0, len = array.length; i < len; i++) {
if(array[i] === x) {
pos = i;
}
}
return pos;
}相信大家都可以看出来，该函数的功能是在一组无序数组中查找元素 x，如果存在，就返回下标，否则返回 -1。按照之前的方法分析，这段代码的时间复杂度为 O(n)，其中，n 代表数组的长度。
我们在数组中查找数据，并不需要每次都把数组全部遍历一遍，因为中途就找到目标元素的话就可以提前终止循环了。下面我们再优化一下代码：
function find(array, x) {
let pos = -1;
for(let i = 0, len = array.length; i < len; i++) {
if(array[i] === x) {
pos = i;
break;
}
}
return pos;
}问题来了，我们优化之后的 find 函数的时间复杂度还是 O(n) 吗？很显然不是了，如果我们要查找到元素位于数组的第一个，那么它的时间复杂度就是 O(1)，如果位于末尾，那么时间复杂度就是 O(n)。所以，在不同情况下，这段代码的时间复杂度是不一样的。
为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度。
顾名思义，最好情况时间复杂度，就是在最理想的情况下，执行这段代码的时间复杂度。在上述代码中，最理想的情况就是我们要查找的元素 x 正好位于数组的第一位，这时对应的时间复杂度就是最好情况时间复杂度。
同理，最坏情况时间复杂 6105 ，就是在最差的情况下，执行这段代码的时间复杂度。还是拿上述例子来说，如果元素 x 不在数组中，我们需要把整个数组都遍历一遍才行，这是对象的时间复杂度就是最坏情况时间复杂度。
平均情况时间复杂度
我们都知道，最好最坏情况时间复杂度都是在极端情况下的时间复杂度，发生的概率其实都不大，为了更准确的表示时间复杂度，我们需要引入第三个概念：平均情况时间复杂度。
还是借助上面的例子，要查找的变量 x 在长度为 n 的数组中的位置，有 n + 1 中情况：在数组 0 ~ n - 1 位置中和不在数组中。我们把每种情况下，需要查找遍历的元素个数累加起来（等差数列求和），再除以 n + 1，就可以得到需要遍历元素个数的平均值，即：
时间复杂度的大 O 表示法中，可以省略掉系数、低阶、常量。所以，该公式简化之后，可以得到平均情况时间复杂度 O(n)。