时间复杂度分析-下

参考文章来源： 极客时间

之前总结了一下时间空间复杂度分析，描述了时间复杂度和空间复杂度的分析方法，今天再总结一下最好情况时间复杂度、最坏情况时间复杂度、平均时间复杂度和均摊时间复杂度。

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

先举个栗子：

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

这段代码的功能是从数组中查找特定元素的位置（假设数组中存放的元素不会重复）。试着分析一下这段代码的时间复杂度和空间复杂度。很简单，时间复杂度是O(n)，因为里面只有一个for循环，for循环的次数是n，当n无线大时，时间复杂度就是O(n)。因为程序执行过程中没有另太开辟内存空间，所以它的空间复杂度是O(1)。

其实这段代码有改进的空间，因为在for循环内，只要找到了指定的元素，我们就可以退出循环，返回程序，因此上面的代码可以改进一下：

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

那么，优化后的代码时间复杂度是多少呢？这个就不好判断了，因为for循环的执行次数是不确定的，这取决于要查找的元素的位置，此时我们可以将时间复杂度分为以下三种情况，同时也就引入了三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

最好情况时间复杂度 就是在最理想的情况下代码的时间复杂度，上面代码的最理想情况就是要查找的元素就是数组的第一个元素，此时代码的时间复杂度就是代码的最好情况时间复杂度。

最坏情况时间复杂度 就是在最糟糕的情况下代码的时间复杂度，上面代码的最坏情况就是数组中没有要查找的元素，此时代码的时间复杂度就是最坏情况时间复杂度。

平均时间复杂度我们接下来单独拿出来说。

平均情况时间复杂度

最好和最坏时间复杂度都是最极端的情况，为了更好地表示大多数情况下代码运行的效率，我们引入了 平均时间复杂度 的概念，即平均情况下代码的时间复杂度。

以上面的例子为例，一共有n+1种情况：要查找的元素在数组0~n-1的位置和不在数组中，把每种情况下要查找的元素个数累加起来然后处以n+1,就可以得到需要遍历元素的平均值，也就是：

平均值

使用大O表示法，去掉系数、低阶、常量，最后平均时间复杂度就是O(n)。

这种计算方法存在一个问题，就是每种情况发生的概率是不同的。如果引入概率问题，假设数据在数组和不在数组的概率都是1/2，同时也假设元素在数组0~n位置的概率也一样为1/n。那么如果要元素在数组内，每种情况发生的概率就是1/2n，如果元素不在数组内，发生的概率就是1/2。

此时时间复杂度就变成了下面这样：

复杂度概率

引入概率后，上面代码的平均时间复杂度变为O(3n/4)，去掉系数、低阶、常量，最后仍然是O(n)。

大多数情况下并不需要区分最好、最坏、平均时间复杂度，只有在同一段代码在不同情况下时间复杂度存在量级差别时，才需要区别对待。

均摊时间复杂度

这里还有一个更高级的概念叫均摊时间复杂度。均谈复杂度分析应用的场景想对于上面介绍的三种更加特殊，也更加有限。

再举个栗子：

// 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，插入的位置存在n中情况，每种情况下时间复杂度都是O(1)。两外还有一种情况:数组中没有空余空间，这个时候的时间复杂度是O(n)。这n+1中情况发生的概率相等，都是1/n，那么最后加权后，平均复杂度就变成了下面这样：

平均复杂度

这里分析时间复杂度可以不用这么复杂，对比一下这个insert函数和find函数，可以发现两者存在一个很大的差别：find函数大多数情况下时间复杂度都不是O(1)，insert函数大多数情况下时间复杂度是O(1)。

针对这种情况，可以引入一种更加简单的分析方法：摊还分析法，通过这种方法得到的时间复杂度我们称之为均摊时间复杂度。

在插入数据时，每一次O(n)的插入操作，都跟着n-1次O(1)的插入操作，所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，就会降低O(n)的时间复杂度，最后在数据量无线增大的过程中逐渐趋进于O(1)。

均摊时间复杂度分析应用场景特殊，我们不会经常用到，一般情况下只在以下场景下适用：

对一个数据结构进行一组连续操作，大部分情况下时间复杂度都很低，个别情况下时间复杂度比较高，且操作之间存在前后连贯的时序关系。一般情况下均摊时间复杂度就等于最好情况时间复杂度。

看看就好，均摊时间复杂度不需要花费太多精力。

总结

这里分析了几种时间复杂度概念：最好、最坏和平均时间复杂度，以及最后介绍了均摊时间复杂度。引入不同时间复杂度的原因是代码在不同场景下的时间复杂度可能差别很大。然后从示例代码出发介绍了几种时间复杂度的分析方法，最好、最坏情况时间复杂度比较简单，平均、均摊时间复杂度相对复杂。

2019.01.14 北京晴雾霾很大