最好、最坏、均摊，这都是啥？

今晚月高风黑，卡卡又去豆豆的小卖部买东西，发现很多东西摆在一个货架上，掰着手指头数了数，总共有十层高。

“豆豆，我想要买零食，哪个好吃？有没有推荐的！”

“豆豆运营产品，都好吃～”

“那我要两包红牛辣条，一包猫耳朵”

“都在货架上，你自己找找看”

卡卡扫了一眼，正好在货架第一层看到辣条，顺手拿了两包，然后接着往上找，在最后一层找到猫耳朵，悠悠的说了一句：“猫耳朵薯片挂这么高，你怕是要上天哦～”

上面这件小事转化为代码，如下所示：

// n表示货架的层数,storage表示上面摆放的货物，x表示需要找的东西
public int findfood(int[] storage, int n, int x ){
  // 表示从第一层开始寻找
  int i = 1;
  for(;i <= n; i++){
    if(storage[i] == x){
      // 找到需要的东西，直接返回所在位置，终止程序
      return i;
    }
  }
  // 找遍货架也没找到需要的东西，返回-1
  return -1;
}

我们从代码上看，结合上节课的内容，这段代码最大的循环是n，那么它的复杂度是不是是O(n)呢？

卡卡在拿辣条的时候，从第一层就发现了辣条的位置，剩下的层数就不用看了，这时候的时间复杂度可以记做O(1)，这只用了一次比较，堪称最快速度。

但是在找猫耳朵薯片的时候，却需要把整个货架找一遍，这时候的时间复杂度可以记作O(n)。

这时候我们需要打开一扇新的大门，引入一些新的知识：最好时间复杂度、最坏的时间复杂度和平均时间复杂度。

最好时间复杂度就是最理想的状态下，执行代码的时间复杂度。就像卡卡在第一层正好找到辣条的位置。

最坏时间复杂度就是最坏的情况下，执行代码的时间复杂度。就像卡卡把整个货架找了一遍，在最后才找到猫耳朵，另外找一遍都找不到才是最坑的。

平均时间复杂度，这个该怎么说呢？

就像卡卡去小卖部买零食，辣条出现的位置可能在每一层，我们需要把在每一层出现时，查找所需要的时间加起来，然后再除以所有的次数之和。求出来的平均值就是平均之间复杂度。

在计算的过程中，别忘了一种最糟糕的情况，就是找了一遍最后发现没找到，下架了！

忽略掉系数以后，我们把得到的结果简化以后，得到的结果就是O(n)。

是不是感觉就要学会了，但是别忘了另外一件事情，那就是每个可能出现的概率一定是一样的吗？

简单的来说辣条放在第三层的是有一个前提条件的，那就是辣条是没下架的。那基础状态就有两种，下架和未下架，假设它们的概率都是50%。当辣条没有下架时，它存在每一层的概率都是相等的，可以成为1/n，所以要找的辣条存在第1～n层的概率就是1/(2n)。

这时候的平均复杂度就会变成下面这样子：

这种求平均值的方法，在数学里面称为加权平均值， 也叫做期望值。所以这样子算出来的平均时间复杂度也就是加权平均时间复杂度或者期望时间复杂度。

这个时间复杂度去掉的系数以后也变成了O(n)。分析的过程有些复杂，但是不是所有的场景都需要分析全部的时间复杂度的，具体实例要具体分析。

均摊时间复杂度

这个听起来是不是和平均时间复杂度很接近，但这完全是两个不同的概念。

豆豆对小卖部的零食做了统计，把每层货架上有哪些零食做了一张表格，贴在门口。

大家来采购的时候，只要瞅一眼表格，就能知道什么零食放在什么位置，这个时间复杂度直接优化到了O(1)级别，这个操作秀啊。

隔壁的小伙伴总会来采购零食，他们每次都会派一个代表人员来采购，他们寝室很多人都会看表格找零食的位置，都能很快找到东西。

如果是小王来的话，小王啊这个人比较懒，不喜欢看表格，会把货架从下往上看一遍，那么隔壁寝室轮流采购的时间复杂度该怎么计算呢？

最好的情况就是在表格上可以直接找到，然后直接去拿东西，这时候的时间复杂度就是O(1)，那么最糟糕的就是小王，时间复杂度记做O(n)，平均时间复杂度该怎么计算呢？

这些人的所有概率都是一样的，唯独小王的时间复杂度是O(n)，加权求出来的平均值时间复杂度就变成了O(1)。

我们再来看一下这个采购流程，只能当小王这种个例出现的时候，才会出现更加复杂度更高的情况，也就是O(n)，大部分情况下的时间复杂度都是O(1)。

第二点就是这里很有规律，寝室里面人轮流一圈的时候，总会出现小王来采购，这出现的频率是非常有规律的，而且有一定的先后顺序。

一般是n-1个O(1)，紧接着一个小王的O(n)，然后循环一遍又一遍。

针对这种特殊的情况，我们可以不用复杂的概率方法去求平均时间复杂度。我们可以使用更加简单的分析方法：摊还分析法，也称为平摊分析。

简单来说，我们现在要知道隔壁寝室的平均时间复杂度，这时候我们可以把小王的时间复杂度均摊到其他室友身上。就是把每次O(n)的时间分到 n-1 的人上面，这样一顿骚操作下来，隔壁寝室轮流一圈的采购零食的均摊时间复杂度就是O(1)。

均摊时间复杂度就是一种特殊的平均时间复杂度。对一个数据结构进行一组连续操作。