数据结构与算法之美（三）复杂度分析（下）

04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度

• 最好情况时间复杂度（best case time complexity）
• 最坏情况时间复杂度（worst case time complexity）
• 平均情况时间复杂度（average case time complexity）
• 均摊时间复杂度（amortized time complexity）

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

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

以上代码，是在一个无序数组 array 中，查找变量 x 出现的位置，找不到则返回 -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;
}

现在这段代码的时间复杂度还是 O(n) 么？

• 当数组中第一个元素刚好是要查找的变量 x ，那此时的时间复杂度就是 O(1)
• 当数组中不存在变量 x ，那么整个数组都需要遍历一遍，时间复杂度是 O(n)
  为了表示代码在不同情况下的不同时间复杂度，引入三个概念：最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度

平均情况时间复杂度

从上面的例子看，想要查找变量 x 在数组中的位置，有 n + 1 种情况：在数组的 0 ～ n - 1 位置 和 不在数组中。每种情况下，查找所需遍历元素的个数累加 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n + n ，除以 n + 1，就能得到需要遍历元素个数的平均值，即 n(n+3)/2(n+1)，时间复杂度的大O表示法中，忽略系数、低阶、常量，所以这个公式简化后得到的平均情况时间复杂度为O(n)

但是，上述计算过程没有将概率考虑进去。🤔🤔🤔考虑概率怎么计算呢......

设变量 x 在数组中的概率是 p ，则不在数组中的概率为 1-p，那么，在数组中各个位置的概率应均为 p/n
那么，平均时间复杂度的计算过程应该是这样的：
1 * p/n + 2 * p/n + ... + (n-1) * p/n + n * p/n + n * (1-p)
经计算，可简化为：n(2-p)/2 + p/2，这就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该是加权平均时间复杂度或者期望时间复杂度。

⚠️注意：这里和王争老师讲的不一样啦，王争老师的计算结果是(3n+1)/4，他的计算过程可理解为：为了计算方便，假设 p=1/2，将其代入我的公式也可得出相同结果。✌️

引入概率之后，用大O表示法表示，去掉公式n(2-p)/2 + p/2中的系数 (2-p)/2 和常量 p/2 ，上例的加权平均时间复杂度仍然是 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 == array.length 时，遍历数组求各项和，将 sum 放到数组第一个位置，然后将新的数据插入。如果数组有空闲空间，则直接将数据插入数组。

• 最好情况时间复杂度：数组中有空闲空间，只需将数据插入到数组下标为 count 的位置，此时时间复杂度 O(1)
• 最坏情况时间复杂度：数组中没有空闲空间，需要遍历数组求各项和，再将数据插入，此时时间复杂度为 O(n)
• 平均情况时间复杂度：数组长度是 n ，根据数据插入位置的不同，有n 种可能性，这些情况的时间复杂度均为 O(1) ；还有一种数组没有空闲空间的情况，这种情况的时间复杂度是 O(n) 。这 n+1 种情况发生的概率均为 1/(n+1)。所以，根据加权平均的计算方法，求得平均时间复杂度是：
  1 * 1/(n+1) + 1 * 1/(n+1) + ... + 1 * 1/(n+1) + n * 1/(n+1)，即 O(1)

对比以上 find() 和 insert() 两个函数：

1. find() 函数最好情况下时间复杂度才为 O(1) ，其平均情况时间复杂度为 O(n) ；而 insert() 函数的平均情况时间复杂度就是 O(1) ，只有个别情况下复杂度较高，为 O(n) 。
2. 对于 insert() 来说， O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是有规律可循的，并且有一定的先后时序关系。一般是 O(n) 插入之后，紧跟着 n - 1 个 O(1) 的插入操作，循环往复。

所以，针对 insert() 函数这种特殊场景的复杂度分析，引入了更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度叫作均摊时间复杂度。

均摊时间复杂度就是一种特殊的平均时间复杂度。

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

均摊时间复杂度和摊还分析应用场景比较特殊：

1. 对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高
2. 这些操作之间存在前后连贯的时序关系

符合上面两条的场景下，可以将这一组操作一块儿分析，看是否能将时间复杂度较高的那次操作的耗时分摊到其他时间复杂度较低的操作上。

在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

课后思考

用今天学到的来分析一下下面代码中 add() 函数的时间复杂度

// 全局变量，大小为 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;
}

思考思考吧～🤔