算法-最好、最坏、平均、均摊时间复杂度

发表于 | 更新于 | 分类于 | 阅读次数：

前言


前面我们讲过复杂度的大O表示法和几个分析技巧，还举了一些复杂度分析的例子，掌握了这些内容，对于复杂度分析这个知识点，已经达到及格线了。

这篇会着重讲一下复杂度分析的四个复杂度分析方面的知识：

最好时间情况复杂度、最坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度。


最好、最坏时间复杂度


我们先用学过的知识试着分析以下代码的时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
int findArray(int[] arr, int n, int target){
  int i = 0;
  int pos = -1;

  for(i; i<n; i++){
    if(arr[i] = target){
      pos = i;
    }
  }
  return pos;
}

上面代码实现的功能是在一个无序数组中，查找变量target的位置，如果找不到就返回-1，按照前面的分析方法，该段代码的时间复杂度为O(n)。

但是我们在数组中查找一个数据，并不需要每次都把整个数组都遍历一遍，优化一下这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
int findArray(int[] arr, int n, int target){
  int i = 0;
  int pos = -1;

  for(i; i<n; i++){
    if(arr[i] = target){
      pos = i;
      break;
    }
  }
  return pos;
}

但是这时候问题来了，优化完之后，时间复杂度还是O(n)吗？

因为要查找的变量target可能出现在数组的任何位置，如果要查找的target刚好出现在数组的开始位置，那么就不需要遍历剩余的数据，此时时间复杂度为O(1)。但是如果数组中不存在变量target，或者在最后一位，那我们就需要把整个数组都遍历一遍，时间复杂度就成了O(n)，所以这段代码在不同情况下时间复杂度是不同的。

为了表示代码在不同情况下的时间复杂度，我们需要引入三个概念：最好情况时间复杂度、最坏情况复杂度、平均时间复杂度。

顾名思义，最好情况时间复杂度就是，在最理想情况下，执行这段代码的时间复杂度。如上例中，在最理想情况下，查找的变量target刚好在第一个，这时候对应的时间复杂度就是最好情况时间复杂度。

同理，最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度，上例中，如果数组中没有要查找的变量target，我们需要把整个数组遍历一遍，所以最坏情况下对应的时间复杂度就是最坏情况复杂度。


平均时间复杂度



我们都知道，最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率并不大。为了更好的表示平均情况下的时间复杂度，我们引入一个概念：平均情况时间复杂度，简称平均时间复杂度。

平均时间复杂度又该怎么分析呢？我们还是借助上面的例子。

要查找的变量target在数组中的位置，有n+1中情况： 在数组0 ~ n-1位置 n种情况和不在数组中1个情况。我们把每种情况下，需要遍历的元素个数累加起来，然后在除以n+1，就可以得到需要遍历的元素个数的平均值，即：

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

我们知道，时间复杂度大O标记法中，可以省略掉系数、低阶、常量，所以上面的时间复杂度为O(n)。

这个结论虽然是正确的，但是计算过程稍微有点问题。我们刚讲的这n+1中情况，出现的概率并不一样。下面结合概率论的知识分析一下。

我们知道，要查找的变量x，要么在数组中，要么不再数组中，我们假设这两个概率分布为$\frac{1}{2}$。

不在数组中时，时间复杂度为: $n\times\frac{1}{2}$; 在数组中时，因为数组大小为n，出现在任何一个位置的可能性都是一样的，所以每个位置的概率就是:$\frac{1}{2n}$, 因此在数组中时的时间复杂度为：$(1+2+3+…+n)\times\frac{1}{2n} $。

那平均时间复杂度就是：$(1+2+3+…+n)\times\frac{1}{2n} + n\times\frac{1}{2} = \frac{3n+1}{4} = O(n)$。

这个值就是概率论中的加权平均值，也叫做期望值，所以平均时间复杂度也叫做加权平均时间复杂度或者期望时间复杂度。

实际上，在大多情况下我们并不需要区分最好、最坏、平均时间复杂度三种情况，很多时候我们只用一个复杂度就可以满足需求了。只有同一代码在不同的情况下，时间复杂度有量级的差距，我们才会使用三种复杂度表示法来区分。


均摊时间复杂度



目前为止，我们应该已经掌握了算法复杂度分析的大部分内容了，下面来认识一个更高级的概念：均摊时间复杂度，以及它对应的分析方法摊还分析。

均摊时间复杂度听起来跟平均时间复杂度有点像，对于初学者来说，这两个概念很容易弄混。前面说过，大部分情况下不需要区分最好、最坏、平均时间复杂度，只有某些特殊情况才需要平均时间复杂度，而均摊时间复杂度比它的应用场景比它更特殊、更有限。

还是以一个例子来说明(别太在意例子，只是为了说明)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] arr = new int[n];
int size = 0；

void insert(int val){
  // 如果数组满了
  if(count == arr.length){
    int sum = 0;
    for(int i=0; i<arr.length;i++){
      sum = sum + arr[i];
    }
    arr[0] = sum;
    count = 1;
  }
  // 数组赋值
  arr[count] = val;
  ++count;
}

先简单解释一下这段代码的功能，这段代码实现了一个往数组中插入数据的功能，如果数组有空闲空间，直接插入即可。如果数组满了，将数组中的数据求和，清空数组，将求和之后的数据放入数组的第一个位置，然后再将新的数据插入。

那这段代码的时间复杂度是多少呢？我们可以先利用上面讲的三种分析方法来分析一下。

最理想情况下，数组有空闲空间，直接插入数据就可以，所以最好时间复杂度为O(1)；最坏情况下，数组中没有空闲空间了，我们需要先进行一次数组遍历求和，在做数据插入，所以最坏情况时间复杂度为O(n)；平均情况时间复杂度，我们还是用概率论的方法来分析，假设数组长度为n，根据插入位置不同，可以分为n种情况，每种情况的时间复杂度为O(1)，另外还有一种特殊情况，就是数组没有空闲时间时，时间复杂度为O(n)，而且这n+1中情况出现的概率是一样的，所以根据加权平均的计算方法，求得平均时间复杂度为：$ 1\times\frac{1}{n+1} + 1\times\frac{1}{n+1} + 1\times\frac{1}{n+1} +….+ 1\times\frac{1}{n+1} + n\times\frac{1}{n+1} = O(1) $。

我们来比较一下这个例子中insert函数和上面findArray的不同。首先，findArray在极端情况下，复杂度才为O(1)，大部分情况都为O(n)，而insert函数大部分情况时间复杂度都为O(1)，只有特殊情况时间复杂度才为O(n)，这是第一个区别。第二个不同的地方，对于insert函数来说，O(1)和O(n)的时间复杂度出现的频率是非常有规律的，而且有一定的时序关系，一般都是一个O(n)插入之后，跟n-1个O(1)的插入操作，循环往复。

针对这样一种情况，我们并不需要像平均复杂度分析那样，计算所有输入情况和发生的概率，计算加权平均值。 我们引入一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度我们起了一个名字叫：摊还时间复杂度。

那么究竟如何使用摊还分析法来分析算法的均摊时间复杂度呢？

我们还是以这个insert函数为例，每一次O(n)的插入操作，后面都会跟n-1次O(1)插入操作，所以我们把耗时最多的操作均摊到n-1次耗时少的操作上，均摊下来，这一组连续操作的均摊时间复杂度就为O(1)，这就是均摊分析法的大致思路。

均摊时间复杂度和摊还分析应用场景比较特殊，所以不会经常用到，这里简单总结一下他们的应用场景。

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块分析，看看是否能将时间复杂度高的操作，均摊到其他时间复杂度低的操作上。在一般的能运用均摊时间复杂度的场景中，均摊时间复杂度是等于最好时间复杂度的。

思考题：

根据今天学习的几个复杂度分析的方法，来分析一下下面这个add()函数的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int[] arr = new int[10];
int len = 10;
int i=0;

void add(int element){
  // 数组空间满了
  if(i>=len){
    // 数组扩容
    int new_arr = new int[len*2];
    // 把数组拷贝到新数组
    for(int j=0; i<len; j++){
      new_arr[j] = arr[j];
    }
    arr = new_arr;
    len = len*2;
  }
  // 添加到数组中
  arr[i] = element;
  ++i;
}

分析：在最理想情况下，数组中有空闲空间，可以直接添加到数组中，时间复杂度为O(1)；最坏情况下，数组中没有空闲空间，先进行一次扩容操作，在进行遍历给新数组赋值，时间复杂度为O(n)，所以最坏时间复杂度为O(n)。

平均时间复杂度，可以分为有空闲空间和没有空闲空间两种，有空间空间有n中情况，所以每种情况出现的概率为$\frac{1}{n+1}$，所以根据加权平均的计算方法，求得平均时间复杂度为：$ 1\times\frac{1}{n+1} + 1\times\frac{1}{n+1} + 1\times\frac{1}{n+1} +….+ 1\times\frac{1}{n+1} + n\times\frac{1}{n+1} = O(1) $。

均摊时间复杂度，可以看出本例是符合均摊时间复杂度的场景的，在一次O(n)时间复杂度操作后都会跟n-1次O(1)时间复杂度操作，所以将O(n)时间复杂度的操作均摊到n-1次O(1)时间复杂度操作上，最终均摊时间复杂度为O(1)。