序
上一篇博客《怎么计算时间和空间复杂度?》讲了基本的算法复杂度怎么算。但是如果我们碰到复杂一点的代码，有时候还是会不够用。
比如这一段代码：
function find($arr, $n, $x) {
$pos = -1;
for ($i = 0; $i < $n; ++$i) {
if ($arr[$i] == $x) {
$pos = $i;
break;
}
}
return $pos;
}
这段代码要实现的功能是：在一个数组$arr中，找出变量$x的位置。
因为，变量$x可以出现在任何位置。如果第一次就查找到了，就是O(1)，如果最后一次才查找到那就是O(n)。不同情况下，这段代码的时间复杂度是不一样的。
所以，这里我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度。
最好、最坏时间复杂度
最好最坏时间复杂度非常好理解。顾名思义，最好时间复杂度，就是在最理想情况下的时间复杂度。同理，
最坏时间复杂度，就是在最糟糕情况下的时间复杂度。
平均时间复杂度
最好、最坏时间复杂度属于极端情况下的时间复杂度。一般来说，发生概率不大。为了更好的表示时间复杂度，还引入了一个概念：平均时间复杂度。
平均时间复杂度也不难理解。就是将每种情况的时间复杂度相平均计算。
同样用上面的例子。要查找$x的位置，一共有n+1中情况：在数组中0～n-1和不在数组中。我们把每种情况需要执行的次数相加，再除以总的次数，就是平均时间复杂度。
(1+2+3+4+ ... +n+n) / (n+1) = n(n+3) / 2(n+1)
简化之后，即可得平均时间复杂度为：O(n)。
这个结论虽然正确。但是较正的话还是有问题的，当然如果只是说平均时间复杂度的思想，已经说的很清楚了。
问题在哪里呢？问题就是没有把概率没有统计进去。为了方便理解，我们把$x在数组中和不再数组中概率都为百分之五十。
当在数组中时，概率为1/2n。而不在数组中时，概率为1/2。
即可得：
(1 x (1/2n) ) + (2 x (1/2n) ) + (3 x (1/2n) ) + ... + (n x (1/2n) ) + (n x (1/2) ) = （3n+1) / 4
当然，计算出来的平均时间复杂度也为0(n)。
均摊时间复杂度
均摊时间复杂度，是一个更高级的概念，它其实就是平均复杂度的一种。它对于的分析方法是：摊还分析（或称平摊分析）。
摊还分析法，其实也是跟字面上的意思一样。就好比你有5个苹果，分摊给4个小伙伴一人一个。这就是平摊。
同理，在复杂度分析中，我们会将最多执行次数的项，平摊到其他项。但是这个一般应用场景比较特殊：一般是有一个或几个项明显多于其他项的时候。 就像是，你的苹果明显多于其他人，才进行平摊。
我们也用一个例子来具体讲下均摊时间复杂度的计算：
$array = [];
$count = 0;
function insert($val) {
if ($count == count($array)) {
int $sum = 0;
for (int $i = 0; $i < count($array); ++$i) {
$sum = $sum + $array[$i];
}
$array[0] = $sum;
$count = 1;
}
$array[$count] = $val;
++$count;
}
在这个例子中。每一次o(n)的操作之后，会有n-1个o(1)操作。
按之前的方法，我们可以知道：最好时间复杂度是O(1)、最坏时间复杂度是o(n)。平均时间复杂度会相对比较复杂：
(1 x 1/(n+1)) + (1 x 1/(n+1)) + (1 x 1/(n+1)) + ... + (1 x 1/(n+1)) + (n x 1/(n+1)) = O(1)
那么用摊还分析呢：将O(n)均摊到后面n-1个操作中。首先是0(n)平摊后变成O(1)，然后其他n-1个操作，每一项加一次，常数并不会影响时间复杂度， 依旧还是O(1)。所以均摊时间复杂度也是O(1)。
很明显，在这种情况下，摊还分析方便很多。而且均摊时间复杂度跟平均时间复杂度也是一样的。所以我们一般均摊时间复杂度和平均时间复杂度只计算一个就行了。 而且是哪种方式求解比较容易就用哪个。