上一篇文章学习了:如何分析、统计算法的执行效率和资源消耗? 点击链接查看上一篇文章:复杂度分析上

今天的文章学习以下内容:

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

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

这段代码很简单:就是在一个数组中找到一个数X的下标,将其返回。

利用上一篇文章学习的大O表示法来分析时间复杂度的话,有一些问题。if循环中有一个breadk语句,当条件成立,得到下标值立马退出循环。那么时间复杂度,就不能笼统的说是O(n)。

因为当想要查找的数就在第一个位置时,时间复杂度实际上是O(1),当想要查找的数在最后一个位置的时候,时间复杂度是O(n)。那么这个时候,我们就需要引入几个新名词:最好情况时间复杂度,最坏情况时间复杂度。

很容易理解。

  • 最好情况时间复杂度就是在最理想的情况下,执行代码需要的时间复杂度。就像上述代码,如果想要查找的数就是数组中的第一个位置,那么时间复杂度就是O(1),此时就是最好情况时间复杂度。
  • 最坏情况时间复杂度是在最不理想的情况下,执行代码需要的时间复杂度。还是如上述代码,入股我们想要查找的数在数组的最后一个位置,那么时间复杂度就是O(n),此时就是最坏情况时间复杂度。

其实还有一种情况,就是我们想要查找的数不在第一个位置也不在最后一个位置的时候。此时的时间复杂度是多少呢?这种情况下叫做平均情况时间复杂度

那么平均情况时间复杂度如何计算?它是多少呢?

2、平均情况时间复杂度

还是拿上面的代码做例子。

想要计算出它的平均情况时间复杂度,有两种方法,一种不严谨的感官上的方法,一种严格的概率上的方法。

  1. 不严谨的感官上的方法

我们知道,想要查找的数据x有两种情况的存在,一种是存在数组的0~n-1的某一个位置(n种可能),一种是不在这个数组中(1中可能,就是不在数组中)。这两种情况一共有n+1种可能。对于在数组中的n中可能中,每一种查找的次数分别是1,2,3,4…n。对于不在数组中的这种可能,查找次数是n。所以可以这么计算平均情况时间复杂度:

(1+2+3+...+n+n)/(n+1)=n(n+3)/2(n+1)

上一篇文章我们知道,利用大O表示法,,可以将计算结果的系数,低阶,常量去掉。那么上述的结果就是O(n)。

为什么说他不严谨呢?考虑以下情况。要找的数x存在于数组中与不存在于数组中的概率是否一样?x存在的话。它存在于数组中每个位置的概率是否一样?

很明显,上述方法没有考虑概率的问题。

  1. 概率的方法

现在假设,x出现在数组中与不出现在数组中的概率是相等的,都是1/2.同时假设x如果出现在数组中,则它存在数组中的每一个位置的概率都是一样的1/n。那么可以用如下方法计算平均情况时间复杂度。

1 × 1 n × 1 2 + 2 × 1 n × 1 2 + 3 × 1 n × 1 2 + . . . + n × 1 n × 1 2 + n × 1 2 = 3 n + 1 4 (1 \times \frac{1}{n} \times \frac{1}{2}+2 \times \frac{1}{n} \times \frac{1}{2} +3 \times \frac{1}{n} \times \frac{1}{2} +...+n \times \frac{1}{n} \times \frac{1}{2} + n \times \frac{1}{2})= \frac{3n+1}{4} 1×n1×21+2×n1×21+3×n1×21+...+n×n1×21+n×21=43n+1

利用大O表示法来表示的话,依然是O(n)。这就是上面那段代码的平均情况时间复杂度。

一般情况下,我们只是用其中一种复杂度来分析问题就够了,不需要费力去求解三种时间复杂度。只有在时间复杂度有量级的差距时,才会在不同的情况下使用不同的时间复杂度。

3、均摊时间复杂度

上面学会了最好最坏与平均时间复杂度。还有一种时间复杂度叫做均摊时间复杂度。 为了理解均摊时间复杂度,我们先来看一个代码:

 // 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,往数组插入数据会有两种情况发生。数组没满时,插入的时间复杂度是O(1),且插入的位置有n种可能。数组满时,插入的时间复杂度是O(n),插入的位置只有一种可能。所以一共有n+1种可能插入的位置,且插入到它们位置的概率是一样的都是1/(n+1)。所以可以利用下面的方法计算平均情况时间复杂度:
1 × 1 n + 1 + 2 × 1 n + 1 + 3 × 1 n + 1 + . . . + n × 1 n + 1 + n × 1 n + 1 = O 1 (1 \times \frac{1}{n+1}+2 \times \frac{1}{n+1} +3 \times \frac{1}{n+1} +...+n \times \frac{1}{n+1} + n \times \frac{1}{n+1})= O(1) 1×n+11+2×n+11+3×n+11+...+n×n+11+n×n+11=O1

所以

  • 平均情况时间复杂度:O(1)

上述计算平均时间复杂度的方法,不管怎么样,还是有一些复杂。毕竟我们不是研究数学的。所以还是希望尽可能简单。

针对上面的两个代码例子,一个是find函数,一个是insert函数。看看他们有什么不同。find函数是最极端的情况下时间复杂度是O(1),大多数的情况下时间复杂度是O(n),而insert函数是大多数情况下的时间复杂度是O(1),只有极端的情况下时间复杂度是O(n)。

而且,对于insert函数,它的O(1)出现的是连续出现多次,然后出现一次O(n)时间复杂度。这具有一种时序关系。

针对这种情况,给出一种特殊的时间复杂度分析方法,均摊时间复杂度。可以通过摊还分析法,的带均摊时间复杂度。那么针对insert函数,如何通过摊还分析法来得到均摊时间复杂度呢?

首先,对于insert函数,大多是出现O(1)时间复杂度的,一共出现n次O(1)时间复杂度后,才出现一次O(n)时间复杂度。虽然O(n)时间复杂度消耗的时间比较多,但是O(1)时间复杂度出现的次数多,我们可以将O(n)消耗的时间,均摊给其他n个O(1)时间复杂度操作上的话,对于O(1)时间复杂度,也并不会有多大的影响,就好比,100个人共同抬100斤水泥,而另外又有一个人在抬100斤水泥,如果这个人把水泥平均分给那100人,那100人也才每个人多抬了一斤的水泥,这相比让那一个人抬100斤水泥,简直不要太轻松!!!。 所以,对于insert函数均摊时间复杂度为O(1)。这等于大多数情况下的时间复杂度。

综上:

  • 均摊时间复杂度为:O(1)

由以上的分析,我们得出,大概在以下情况下可以使用摊还分析来分析均摊时间复杂度

对一个数据结构进行连续的操作,如果大多数情况下的时间复杂度比较低,只有极端情况下时间复杂度很高,而且这些操作在时序上存在前后连贯的关系。那么此时,就可以将比较耗时的那个操作,均摊给大多数低的时间复杂度的操作上。

而且,一般可以用均摊时间复杂度分析的情况,均摊时间复杂度就等于最好情况时间复杂度

4、总结

上面学习了四种时间复杂度的分析。但是一般来说,平均时间复杂度用的很少,均摊时间复杂度用的就更少。而且,均摊时间复杂度,实际上是一种特殊的平均时间复杂度。

所以不必纠结到底用什么复杂度来分析问题,根据实际问题需要实际分析。对于一段代码,如果它的时间复杂度在不同情况下量级不同,可以采用不同的方法进行对比分析。其中最好最坏时间复杂度比较好分析,平均时间复杂度与均摊时间复杂度比较难分析。

但是对于平均和均摊。他们实际是一个意思,都有平均的意思。当出现O(1)操作的多于O(n)操作的时候,平均和均摊时间复杂度就都是O(1)。 这是一种感觉。一般情况下,我们都可以感觉对,而不用实际的计算。

本文是自己学习极客时间专栏-数据结构与算法之美后的笔记总结。如有侵权请联系我删除文章。

学习探讨加个人(免费送技术书籍PDF电子书):
qq:1126137994
微信:liu1126137994