1、最好与最坏情况时间复杂度

我们首先来看一段代码，利用上一篇文章学习的知识看看能否分析出它的时间复杂度。

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

这段代码很简单：就是在一个数组中找到一个数X的下标，将其返回。

利用上一篇文章学习的大O表示法来分析时间复杂度的话，有一些问题。if循环中有一个breadk语句，当条件成立，得到下标值立马退出循环。那么时间复杂度，就不能笼统的说是O（n）。

因为当想要查找的数就在第一个位置时，时间复杂度实际上是O（1），当想要查找的数在最后一个位置的时候，时间复杂度是O（n）。那么这个时候，我们就需要引入几个新名词：最好情况时间复杂度，最坏情况时间复杂度。

很容易理解。

最好情况时间复杂度就是在最理想的情况下，执行代码需要的时间复杂度。就像上述代码，如果想要查找的数就是数组中的第一个位置，那么时间复杂度就是O（1），此时就是最好情况时间复杂度。
最坏情况时间复杂度是在最不理想的情况下，执行代码需要的时间复杂度。还是如上述代码，入股我们想要查找的数在数组的最后一个位置，那么时间复杂度就是O（n），此时就是最坏情况时间复杂度。

其实还有一种情况，就是我们想要查找的数不在第一个位置也不在最后一个位置的时候。此时的时间复杂度是多少呢？这种情况下叫做平均情况时间复杂度。

那么平均情况时间复杂度如何计算？它是多少呢？

2、平均情况时间复杂度

还是拿上面的代码做例子。

想要计算出它的平均情况时间复杂度，有两种方法，一种不严谨的感官上的方法，一种严格的概率上的方法。

不严谨的感官上的方法

我们知道，想要查找的数据x有两种情况的存在，一种是存在数组的0~n-1的某一个位置（n种可能），一种是不在这个数组中（1中可能，就是不在数组中）。这两种情况一共有n+1种可能。对于在数组中的n中可能中，每一种查找的次数分别是1,2,3,4…n。对于不在数组中的这种可能，查找次数是n。所以可以这么计算平均情况时间复杂度：

(1+2+3+...+n+n)/(n+1)=n(n+3)/2(n+1)

上一篇文章我们知道，利用大O表示法，，可以将计算结果的系数，低阶，常量去掉。那么上述的结果就是O（n）。

为什么说他不严谨呢？考虑以下情况。要找的数x存在于数组中与不存在于数组中的概率是否一样？x存在的话。它存在于数组中每个位置的概率是否一样？

很明显，上述方法没有考虑概率的问题。

概率的方法

现在假设，x出现在数组中与不出现在数组中的概率是相等的，都是1/2.同时假设x如果出现在数组中，则它存在数组中的每一个位置的概率都是一样的1/n。那么可以用如下方法计算平均情况时间复杂度。

$（ 1 \times \frac{1}{n} \times \frac{1}{2} + 2 \times \frac{1}{n} \times \frac{1}{2} + 3 \times \frac{1}{n} \times \frac{1}{2} + . . . + n \times \frac{1}{n} \times \frac{1}{2} + n \times \frac{1}{2} ） = \frac{3 n + 1}{4}$

利用大O表示法来表示的话，依然是O（n）。这就是上面那段代码的平均情况时间复杂度。

一般情况下，我们只是用其中一种复杂度来分析问题就够了，不需要费力去求解三种时间复杂度。只有在时间复杂度有量级的差距时，才会在不同的情况下使用不同的时间复杂度。

3、均摊时间复杂度

上面学会了最好最坏与平均时间复杂度。还有一种时间复杂度叫做均摊时间复杂度。 为了理解均摊时间复杂度，我们先来看一个代码：

 // array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

上述代码的意思是：往数组中插入数据。当数组没有满的时候，直接在最后插入，当数组满的时候，先把数组的所有元素求和，然后清空数组，将求得的和放到数组的第一个位置，然后将要插入的数插到第二个位置（聪明的人已经发现它其实就是一个求输入流中所有数字的和，至于清空数组，这个只是将下标count从末尾挪到第二个位置，就可以认为是清空数组）。

利用上述的分析，我们可以求得：

最好情况时间复杂度：O（1），因为数组不满的时候直接插入，不用计算和。
最坏情况时间复杂度：O（n），因为此时数组满了，需要遍历一遍数组然后求和。

平均时间复杂度，还可以利用上述的概率分析法来计算。假设数组长度是n，往数组插入数据会有两种情况发生。数组没满时，插入的时间复杂度是O（1），且插入的位置有n种可能。数组满时，插入的时间复杂度是O（n），插入的位置只有一种可能。所以一共有n+1种可能插入的位置，且插入到它们位置的概率是一样的都是1/（n+1）。所以可以利用下面的方法计算平均情况时间复杂度：
$（ 1 \times \frac{1}{n + 1} + 2 \times \frac{1}{n + 1} + 3 \times \frac{1}{n + 1} + . . . + n \times \frac{1}{n + 1} + n \times \frac{1}{n + 1} ） = O （ 1 ）$

所以

平均情况时间复杂度：O（1）

上述计算平均时间复杂度的方法，不管怎么样，还是有一些复杂。毕竟我们不是研究数学的。所以还是希望尽可能简单。

针对上面的两个代码例子，一个是find函数，一个是insert函数。看看他们有什么不同。find函数是最极端的情况下时间复杂度是O（1），大多数的情况下时间复杂度是O（n），而insert函数是大多数情况下的时间复杂度是O（1），只有极端的情况下时间复杂度是O（n）。

而且，对于insert函数，它的O（1）出现的是连续出现多次，然后出现一次O（n）时间复杂度。这具有一种时序关系。

针对这种情况，给出一种特殊的时间复杂度分析方法，均摊时间复杂度。可以通过摊还分析法，的带均摊时间复杂度。那么针对insert函数，如何通过摊还分析法来得到均摊时间复杂度呢？

首先，对于insert函数，大多是出现O（1）时间复杂度的，一共出现n次O（1）时间复杂度后，才出现一次O（n）时间复杂度。虽然O（n）时间复杂度消耗的时间比较多，但是O（1）时间复杂度出现的次数多，我们可以将O（n）消耗的时间，均摊给其他n个O（1）时间复杂度操作上的话，对于O（1）时间复杂度，也并不会有多大的影响，就好比，100个人共同抬100斤水泥，而另外又有一个人在抬100斤水泥，如果这个人把水泥平均分给那100人，那100人也才每个人多抬了一斤的水泥，这相比让那一个人抬100斤水泥，简直不要太轻松！！！。所以，对于insert函数均摊时间复杂度为O（1）。这等于大多数情况下的时间复杂度。

综上：

均摊时间复杂度为：O（1）

由以上的分析，我们得出，大概在以下情况下可以使用摊还分析来分析均摊时间复杂度

对一个数据结构进行连续的操作，如果大多数情况下的时间复杂度比较低，只有极端情况下时间复杂度很高，而且这些操作在时序上存在前后连贯的关系。那么此时，就可以将比较耗时的那个操作，均摊给大多数低的时间复杂度的操作上。

而且，一般可以用均摊时间复杂度分析的情况，均摊时间复杂度就等于最好情况时间复杂度

4、总结

上面学习了四种时间复杂度的分析。但是一般来说，平均时间复杂度用的很少，均摊时间复杂度用的就更少。而且，均摊时间复杂度，实际上是一种特殊的平均时间复杂度。

所以不必纠结到底用什么复杂度来分析问题，根据实际问题需要实际分析。对于一段代码，如果它的时间复杂度在不同情况下量级不同，可以采用不同的方法进行对比分析。其中最好最坏时间复杂度比较好分析，平均时间复杂度与均摊时间复杂度比较难分析。

但是对于平均和均摊。他们实际是一个意思，都有平均的意思。当出现O（1）操作的多于O（n）操作的时候，平均和均摊时间复杂度就都是O（1）。这是一种感觉。一般情况下，我们都可以感觉对，而不用实际的计算。

本文是自己学习极客时间专栏-数据结构与算法之美后的笔记总结。如有侵权请联系我删除文章。

学习探讨加个人（免费送技术书籍PDF电子书）：
qq：1126137994
微信：liu1126137994

【数据结构与算法-java实现】二 复杂度分析（下）：最好、最坏、平均、均摊时间复杂度的概念

1、最好与最坏情况时间复杂度

2、平均情况时间复杂度

3、均摊时间复杂度

4、总结

【数据结构与算法-java实现】二复杂度分析（下）：最好、最坏、平均、均摊时间复杂度的概念