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

较为复杂的分析方法大致可分为四类、分别为:最好时间复杂度、最坏时间复杂度、平均时间复杂度和均摊时间复杂度

这里有一段代码,针对它下面分别来说一下怎么算着四种时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
// i的取值范围是 0~n
void add(int element) {
if (i >= len) {
int new_array[] = new int[len*2];
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
array = new_array;
len = 2 * len;
}
array[i] = element;
++i;
}

最好、最坏时间复杂度

最好时间复杂度,言明直意,就是在最好情况下求得的时间复杂度,对于上面代码,针对长度为N的数组添加一个元素的最好时间复杂度为O(1)

在最好情况下,数组空间很充足,可以直接将数组添加到第i位置

在最坏情况下,数组空间不够,所以要重新申请一个2倍大小的数组空间,把原来array数组中的数据依次copy到new_array,因此最坏的时间复杂度应该是O(N)

平均时间复杂度

最好、坏的时间复杂度局限性很大,有时不能准确说明问题,针对这种情况,我们用代码执行各种情况的加权平均值来说明问题。

假设数组的大小为N,i的取值范围为0~N,在0~n-1时间复杂度为O(1),在i等于N的时候时间复杂度为O(N),i的取值有1/(n-1)种可能性,所以有:

06D6CABC-665D-422E-B3A6-CB2C6F1076C9.jpeg

最终平均时间复杂度是O(1)

均摊时间复杂度

网上有好多说平均时间复杂度就是均摊时间复杂度,它们并没有什么区别,不管他们俩是否一样,这边有两个tip来帮助我们算出均摊时间复杂度

  1. 在N种情况中,如果第被低阶复杂度占去了半壁江山,那么通过均摊更高阶的复杂度到低阶上,最终结果为低阶复杂度。
  2. 假如你发现低阶复杂度和高阶复杂度出现规律性的交替,那么通常最终结果为低阶复杂度。

根据上面的tips。很快就得出它的均摊时间复杂度为O(1)

为什么要引入这4种复杂度?

一般我们用不到到这些分析方法,针对某些场景,如果普通的分析方法不能论证我们的论点,那么使用它们往往可以使论点更具有说服力。