引言

Case：分析查找在无序数组n中变量x出现的位置的时间复杂度，因为不同情况下时间复杂度是不同的，如果仅仅是使用T(n) = O(n)，n表示数组长度，并不能很好的表示出对应的复杂度。所以引入最好、最坏和平均三个不同维度的时间复杂度。
1. 最好情况时间复杂度：最理想的情况下，执行代码的时间复杂度，一般是指，执行效率最高的时间复杂度，如：上面案例,第一次就查出了x的值，那么这个时候时间复杂度:T(n) = O(1);
2. 最坏情况时间复杂度：最糟糕情况下，执行代码的时间复杂度，一般是效率最低的时间复杂度，如：数组中，没有x的取值，这时候需要遍历一遍数据组，这时的时间复杂度是：T(n) = O(n)
3. 平均情况时间复杂度：是指大部分情况下，代码执行的时间复杂度;如：查找变量x在数组中的位置，有n+1种情况：在0~n-1位置中和不在数组中。每中情况下需要查找元素个数进行累加再除以n+1，即为平均时间复杂度

$\frac{(1+2+3+...+n+n)}{(n+1)}$ = $\frac{n*(n+3)}{2*(n+1)}$

3.1 加权时间复杂度：因为变量x在数组中和不在数组中发生的概率都是 $\frac{1}{2}$ 的，在数组0~n-1的位置的概率相同都是 $\frac{1}{n}$ ,考虑每种情况发生的概率，那么平均时间复杂度的计算过程变为如下：

$\frac{1+2+3+...+n}{2n}$ +n* $\frac{1}{2}$ = $\frac{1+3n}{4}$

这个值就是概率论中的加权平均值，也叫期望值，所以平均时间复杂度也叫加权平均复杂度或者期望时间复杂度。
3.2 均摊时间复杂度：是一种特殊的平均时间复杂度，针对一个数据结构进行一组连续操作，大部分时间复杂度都很低，个别情况复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这时将这一组操作作为一个整体来进行分析，将复杂度高的均摊到复杂度低的操作上面，这时得到的复杂度就是均摊时间复杂度，对应的分析方法叫做摊还分析法。能够应用均摊时间复杂度的场景，一般情况下，均摊时间复杂度 = 最好情况时间复杂度。

public class TimeComplexity {

    /**
     * 均摊时间复杂度案例
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] array = new int[10];
        int length = 10;
        int i = 0;

        // 循环插入数据
        for (int j = 0; j < 1000; j++) {
            // 往数组中添加元素
            if (i >= length) { // 数组空间不够
                //从新申请一个2倍大小的数组
                int[] newArray = new int[length * 2];
                // 将原来的数据一次拷贝过去。
                for (int k = 0; k < length; k++) {
                    newArray[k] = array[k];
                }
                //
                array = newArray;
                length = length * 2;

            }
            // 将element放到下标为i的位置，下标i+1。
            array[i] = j;
            i++;
        }
        System.err.println(JSON.toJSONString(array, true));
    }

}

小结：大部分情况下不需要关注最好、最坏、平均时间复杂度。只有同一块代码在不同情况下，时间复杂度出现量级差距，我们才会关注上述三种复杂度。