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

上一节具体学习了时间复杂度和空间复杂度，以及对应的分析方法。这节主要从这几个方面入手。

先给个例子解释下面的几个概念

    public int demo (List<Integer> list) {

        for (Integer x : list) {
            if (x == 1) {
                return x;
            }
        }
        return -1;
    }

1. 最好情况时间复杂度（best case time complexity）

在最理想的情况下，执行这段代码的时间复杂度。比如，我们要从一个数组中循环判断是否是我们要的值，第一次就找到了。那么时间复杂度就是O(1);

2. 最坏情况时间复杂度（worst case time complexity）

在最糟糕的情况下，执行这段代码的时间复杂度。假设数组大小为n，直到循环了n次才找到我们要的值。那么时间复杂度就是O(n)，这就是最坏情况时间复杂度。

3. 平均情况时间复杂度（average case time complexity）

最好与最坏是在极端情况下发生的，平均情况复杂度引入了概率，所以也叫加权平均时间复杂度或者期望时间复杂度。
上面说的时间复杂度的平均值即为：

image.png

我们知道，时间复杂度的大 O 标记法中，可以省略掉系数、低阶、常量，所以，咱们把刚刚这个公式简化之后，得到的平均时间复杂度就是 O(n)。

4. 均摊时间复杂度（amortized time complexity）。

在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。