1 最好、最坏时间复杂度

先看下述代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    int find(int[] array, int x) {
        int pos = -1;
        int n = array.length;
        for (int i = 0; i < n; i++) {
            if (array[i] == x) {
                pos = i;
                break;
            }
        }
        return pos;
    }

该代码用于寻找数组中是否含有数 x,如果有则返回数组下标,没有则返回 -1。这段代码在 x 不确定的时候可能第一轮循环就找到了,也可能需要循环整个数组,可能还找不到,所以需要用最好和最坏时间复杂度表示比较贴切。

最好时间复杂度:O(1) 最坏时间复杂度:O(n)

2 平均时间复杂度

还是上面那段代码,由于最好时间复杂度和最坏时间复杂度发生的概率并不大,所以为了更好的表示平均情况下的复杂度,所以需要引入平均时间复杂度。下图是计算平均时间复杂度的过程

计算平均时间复杂度的过程

公式是求平均比对多少个数组元素才能找到 x。如果 x 在第一个位置,那需要比对 1 次,如果在第二个位置,需要比对 2 次,以此类推,如果在第 n 个位置,那就需要比对 n 次。如果不在2数组中,也需要比对 n 次。所有的次数值和除以 n+1 种情况,就是平均比对元素个数。最后去掉系数,平均时间复杂度为 O(n)

这种计算方式有一个问题,就是没有考虑每种情况发生的概率,这里假设每种情况发生的概率为 1/2n,那么计算公式就变成了如下的样子。

计算平均时间复杂度的过程

计算结果便是加权平均值,加权平均时间复杂度依然为 O(n)

3 均摊时间复杂度

先看代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Demo {
    private int[] array;
    int count = 0;

    Demo(int n){
        array = new int[n];
    }

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

如上代码用于将数值插入一个数组,当插入的数组满的时候对数组中的值进行求和然后放到数组索引为 0 的位置上,然后重制数组,循环往复。

先看它的最好、最坏和平均时间复杂度

最好时间复杂度:O(1) 最坏时间复杂度:O(n) 平均时间复杂度:O(1)

针对这种特殊的场景,可以使用摊还分析法,用摊还分析法分析出的时间复杂度叫均摊时间复杂度。

这里在 insert 的时候,只有当 count = array.length 的时候,时间复杂度才为 O(n),其余的情况都为 O(1),而 O(1) 的情况有 n-1 种,O(n) 只有 1 种,将 O(n) 均摊到 n-1 种情况上,时间复杂度就为 O(1) 了。