算法复杂度分析（下）

上一篇讲了大O表示法，以及如何推导大O阶的几个技巧，还讲了几种常见的复杂度分析案例。不过，这还不是复杂度分析的全部，本篇将会继续研究探究复杂度分析的其他四个知识点：最好情况时间复杂度，最坏情况时间复杂度，平均情况时间复杂度，均摊时间复杂度。

最好，最坏情况时间复杂度

先来试着分析下面这段代码的时间复杂度

// 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;
  }
  return pos;
}

这段代码就是为了遍历数组查询x,查到了就返回所在数组的下标。不难看出其时间复杂度为O(n)。

我们考虑到在数组中查找数据有可能第一个查到，有可能在中间某个位置查到，这两种情况都应该终止循环并返回。但是上面这段代码不管哪种情况都继续循环遍历，显然需要优化。优化后代码如下：

// 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(n),显然不对。我们按照x可能出现的位置来分析。 如果x出现在第一个位置那么循环中的代码只需要执行一次就找到了，时间复杂度为O(1)。这种情况就是最理想的情况，我们称此种情况下的时间复杂度为最好情况时间复杂度。 如果x出现在最后一个位置，那么就需要n次查找才能找到x,时间复杂度为O(n)。这种情况显然执行代码次数最多，对应的时间复杂度称为最坏情况时间复杂度。

平均情况时间复杂度

上面所说的最好情况时间复杂度和最坏情况时间复杂度都是极端情况下的复杂度，发生概率较小。为了更好的评估算法在平均情况下的时间复杂度，我们引用平均时间复杂度来表示。

平均时间复杂度如何分析？依旧使用上例中的代码，计算x的平均情况时间复杂度. 查找x在数组中的位置，一共有n+1种可能，大致分为两类情况，一种x存在，一种x不存在。将这两种情况下需要遍历的元素个数加起来除以总数n+1,就可以得到需要遍历的元素个数的平均值。

$\frac{1+2+3+…..n+n}{n+1}$ = $\frac{n(n+1)/2+n}{n+1}$ = $\frac{n(n+2)}{2(n+1)}$

简化后表达式后时间复杂度为O(n)。

但是这种计算方法仍然有问题，因为我们默认每种情况出现的概率相同，这是不符合实际的。其实上述两种情况出现的概率是不同的，x在数组中和不在数组中的概率分别为1/2，而数据出现在0 ~ n-1位置的概率为1/n。所以x出现在0 ~ n-1的位置总的概率为1/2n。所以考虑到每种情况发生的概率可得平均情况复杂度计算公式为 ：

1 × $\frac{1}{2n}$+ 2 ×$\frac{1}{2n}$ + 3 ×$\frac{1}{2n}$ +…+ n × $\frac{1}{2n}$ + n ×$\frac{1}{2}$ = $\frac{3n+1}{4}$

这个结果其实在数学上叫做加权平均值或期望值，也就是说平均情况时间复杂度是指加权平均复杂度或叫做期望平均复杂度。

均摊时间复杂度

均摊时间复杂度是一种较为特殊的时间复杂度评估值，其对应的分析方法叫做摊还分析法。通过以下例子来了解下：

 /* 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;
 }

仔细分析这段代码我们可以得出这段代码是为了给数组赋值，如果数组未满则直接插入，如果数组满了则循环遍历数组求和，将结果存入第一个位置，并清空其他位置。 利用前面所学的几种分析方法来分析该段代码的时间复杂度。 首先最好情况时间复杂度是当数组未满时直接插入数据，所以最好时间复杂度为O（1）。 最坏的情况就是数组满了，数组满后需要循环遍历数组求和，循环部分执行了n次，所以最坏的时间复杂度为O(n)。 再来分析平均复杂度。数组未满时一共有n种数据插入的情况，概率都为1/n，复杂度都为O(1);额外的数组满的时候插入第一个位置，概率1，复杂度为O(n)。所以任意插入一个数据的概率为1/n+1。那么平均时间复杂度为：

1 × $\frac{1}{n+1}$+ 1 ×$\frac{1}{n+1}$ + 1 ×$\frac{1}{n+1}$ +…+ 1× $\frac{1}{n+1}$ + n ×$\frac{1}{n+1}$ = O(1)

实际上针对这种情况采用摊还分析法会更加的方便。所谓的摊还分析法是怎么回事呢？

仔细分析以上代码，我们就会发现每次O(n)操作之后（数组满后清空又腾出了空间）紧接着又会有n-1次O（1）的操作。均摊分析法的思路是将耗时多的那一次操作的时间O(n)均摊到耗时少的n-1次上，这样一组连续的操作的均摊时间复杂度就是O(1)。

事实上均摊复杂度就是一种特殊的平均复杂度，只不过是为了针对这样特殊的情况采用了一种均摊的方法来快捷的分析算法的时间复杂度而已。

实例分析

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个 2 倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来 array 数组中的数据依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 复制给 array，array 现在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 将 element 放到下标为 i 的位置，下标 i 加一
   array[i] = element;
   ++i;
}

采用以上几种分析方法可得： 最好时间复杂度为O(1),最坏时间复杂度为O(n),平均时间复杂度为O（1）,均摊时间复杂度为O(1)。