时间复杂度和空间复杂度(三)

这节来介绍下最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity）。

一、最好时间复杂度和最坏时间复杂度

private int find(int[] arr, int n, int x){

        for (int i =0; i<n; i++){
            if (arr[i] == x){
                return i;
            }
        }
        return  -1;
    }

来简单的看这个代码，当x==0时，恰好第一次就找到了，那么时间复杂度就是O1,；相反，当x==n-1时，那么时间复杂度就是On。

so,最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度,就像上述代码一样x==0
同理，最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。遍历一遍才能找到对应的。

二、平均复杂度

我们都知道，最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，我们需要引入另一个概念：平均情况时间复杂度。

按照上面的代码继续举例，平均复杂度呢，顾名思义就是把每种情况的时间复杂度累加除以总共的次数。
上面的情况，从0~n-1 需要遍历n次，加上不在数组的一次情况，共n+1次。公式如下：

image.png
根据上接说的可以省略常量（大 O 标记法中，可以省略掉系数、低阶、常量），那么此时公式就可以简化为On，即此时平均复杂度为On。（不过这个只是期望值，按照概率论计算也是On）

三、均摊时间复杂度

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度

四、总结

复杂度分析的4个概念
1.最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。
2.最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
3.平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。