02-从四个角度分析时间复杂度

最好和最坏时间复杂度

我们来分析下这两端代码

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) { // n
    if (array[i] == x) pos = i;
  }
  return pos;
}

这个时间复杂度也是O(n),我们可以对上面这段代码进行优化一下

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) { // n
    if (array[i] == x) { 
       pos = i;
       break;
    }
  }
  return pos;
}

从普通情况下分析,这个时间复杂度是O(n)

但是这样并看不出区别,我们可以从两种情况下进行分析

最坏情况下:整个数组都没有找到,那么代码就会执行n次,时间复杂度就是O(n);

最好情况下:第一次就找到了,退出循环,那么循环只执行一次,时间复杂度就是O(1);

所以我们可以看出,在不同情况下,时间复杂度是不一样的

平均复杂时间度

从上段代码可以看出,我们都知道，最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，平均时间复杂度的概念就出来了

我们继续拿上面这段代码进行分析,总共有n+1种情况,分为在数组中找到和没在数组中找到

我们在细分下在数组中找到的情况总和,有n种情况,因为在索引(0~n-1)中都有可能找到

所以我们把数组中找到的和在数组中没找到的情况 总共有 n+1种情况

将在数组中找到的每种情况下查找需要遍历的元素的个数进行相加 和 在数组中没找到的情况下 一起相加 除以 (n+1)中情况

(1+2+3+4+5+6+...+n)+n/n+1

打括号的根据 等差数列公式

我们可以算出化简过后的公式

这就是我们细分过后所产生的时间复杂度,但是我们用大O表示法表示,其大O时间复杂度为O(n)

但是我们这么分析是有点问题的,并没有把每种概率都考虑进去

假设在数组中找到和没在数组中找到的概率分别是1/2

而在数组中找到的概率为1/n,因为在(0~n-1)内每个索引都有可能找到

而没在数组中找到,一定是在数组中找了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;
 }

这个代码执行分为两种情况

1. 数组中有空闲,插入了数据
2. 数组中没空闲,对数组中所有数进行了一个相加求和

最好的情况下,就是数组中有空闲,插入完就结束了,时间复杂度是O(1),

最坏的情况下,开始对数组中进行求和,大家看那个for循环,时间复杂度是O(n)

那平均时间复杂度是啥呢,我们可以继续来算,答案会非常神奇,总情况数有 (n+1)种

概率发生都是一样的,其实都是1/n+1

因为有n+1种情况下,进行一个相乘,发现概率是就是1,所以时间复杂度就是O(1)

首先，find() 函数在极端情况下，复杂度才为 O(1)。但 insert() 在大部分情况下，时间复杂度都为 O(1)。只有个别情况下，复杂度才比较高，为 O(n)。这是 insert()第一个区别于 find() 的地方。

我们再来看第二个不同的地方。对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。

所以，针对这样一种特殊场景的复杂度分析，我们并不需要像之前讲平均复杂度分析方法那样，找出所有的输入情况及相应的发生概率，然后再计算加权平均值。

针对这种特殊的场景，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度我们起了一个名字，叫均摊时间复杂度。
我们还是继续看在数组中插入数据的这个例子。每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)

• 还没有人评论，欢迎说说您的想法！

相关课程

英特尔® OpenVINO™工具套件初级课程

292954 0元 限免

人工智能入门

5075 9.8元 98元 1折

英特尔 OpenCV 初级认证课程

7675 0元 限免