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

8/3/2020 复杂度分析数据结构与算法

# 1.最好、最坏、平均情况时间复杂度

有时候我们分析一段代码的时间复杂度时,并不能很直观的就得出结果,需要结合具体的场合来判断它的平均情况。下面来看一个栗子:

/**
 * 找出给定数组中给定元素的位置,如果找不到返回-1
 * @param arr 给定数组
 * @param target 给定元素
 * @return
 */
public int find(int[] arr, int target) {
  int n = arr.length;
  for (int i = 0; i < n; i++) {
    // 依次遍历数组,如果找到和目标元素相同的值,在返回该值所在下标
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

该栗子是在给定数组中寻找给定元素的位置,如果找到返回下标,结束循环;如果找不到则返回-1。

那么这段代码时间复杂度是多少呢?这就不好直接判断了,因为目标元素在数组中位置的不同导致时间复杂度的不同。针对上面这段代码,时间复杂度分析如下:

1.最好情况时间复杂度:目标元素刚好在数组第一个位置,那么只需要一次就能找到,时间复杂度很明显是常量阶O(1)。

2.最坏情况时间复杂度:目标元素在数组最后一个位置或者不在数组中,那么得需要遍历完整个数组才能得出结果,时间复杂度为O(n)。

最坏情况运行时间是一种保证,那就是运行时间不会再坏了。在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况运行时间。

可以看出来,由于目标元素的位置不同,导致时间复杂度出现量级差异。这种情况下就需要考虑平均情况时间复杂度,下面简单分析下:目标元素如果在数组中,出现的位置有n种情况,加上不在数组中这一种情况,总共 n+1 种情况。每种情况下需要遍历的次数如下表:

第1个位置 遍历1次
第2个位置 2次
第3个位置 3次
第n个位置 n次
不在数组中 n次

由上表可以得出平均遍历次数 = 各种情况遍历次数相加 ÷ 总的情况数。

即遍历次数f(n)与数据规模之间的关系为:

根据大O分析法,忽略低阶项和系数得,T(n) = O(f(n)) = O(n)。所以平均情况时间复杂度为O(n)。

平均情况时间复杂度是所有情况中最有意义的,因为它是期望的运行时间。

# 2.均摊时间复杂度

均摊时间复杂度对应的分析方法叫摊还分析。下面还是以具体的栗子来说明:

/**
 * ${向数组中插入元素,如果数组已满,扩容为原来的2倍}
 *
 * @author WangXiaoLong
 * @version 1.0
 * @create 2018-11-20 0:25
 */
public class IntArray {
    // 记录数组中已有元素个数
    int count = 0;
    // 声明数组
    int[] arr;
    public IntArray(int n){
        // 初始化数组,这里只是举例说明,不考虑n<0等异常情况
        arr = new int[n];
    }
    /**
     * 插入元素
     * @param value
     */
    public void insert(int value) {
        // 数组已经存满,进行扩容操作,然后将之前的元素拷贝到新数组中
        if (count >= arr.length) {
            // 新建一个大小为之前数组2倍的新数组
            int[] arr2 = new int[2*arr.length];
            // 将之前数组中元素copy到新数组中
            for (int i = 0;i<arr.length;i++) {
                arr2[i] = arr[i];
            }
            // 将新数组赋值给原数组(扩容后的数组代替原来的数组)
            arr = arr2;
        }
        // 数组没满,直接将值插入到数组中即可
        arr[count] = value;
        count++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

上面模拟了数组动态扩容的场景,假如数组元素已满,再插入时就新建一个长度为原数组2倍的数组,然后把原数组中的值copy到新数组中,将新数组替换为原数组。化成图解如下:

点击并拖拽以移动

可以分析出来,当数组没满时,插入操作很快,只需要执行1次赋值操作即可,时间复杂度为O(1)当数组已满,需要扩容为原来的两倍,然后将元素数组中的值拷贝到新数组中,假如原数组长度为n,则需要进行n此操作,时间复杂度退化为O(n)

如果细心观察可以发现,每当经历n次时间复杂度为O(1)的操作时,便经历1次时间复杂度为O(n)的操作,有一定的时序规律,并且出现高级别复杂度的情况极少。我们将出现高级别的情况均摊到低级别复杂度的情况中,整个插入操作的时间复杂度就变为O(1)了。这就是摊还分析的大致思想。

总结:

1.代码在不同情况下复杂度出现量级差别,则用平均情况时间复杂度分析。

2.代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度,并且具有一定的时序规律,则用均摊时间复杂度分析。