1.2 不同情况
最好+最坏、平均+均摊（摊还/平摊分析）
代码在不同情况下的时间复杂度：
最好情况时间复杂度
最坏情况时间复杂度
平均情况时间复杂度
概率问题，即加权平均值/期望值
ie.加权平均时间复杂度/期望时间复杂度
1 和 2 都是极端情况下的代码复杂度，发生的概率其实并不大。3 能更好地表示平均情况下的复杂度。
大部分情况下，我们并不需要区分最好、最坏和平均这三种复杂度。只有当同一块代码在不同的情况下，时间复杂度有量级的差距时，我们才会使用这三种复杂度表示法来区分。
the best case time complexity
the worst case time complexity
the average case time complexity
平均复杂度只在某些特殊情况下才会用到，而均摊时间复杂度应用的场景则更加特殊和有限。
amortized time complexity, 均摊时间复杂度
均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多精力去区分它们。最应该掌握的是它的分析方法——摊还分析。至于分析出来的结果是叫平均还是叫均摊，这只是个说法，并不重要。
Last updated