数据结构与算法之美

04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度

基本的四个复杂度:最好情况时间复杂度( best case time complexity )、最坏情况时间复杂度( worst case time complexity )、平均情况时间复杂度( average case time complexity )、均摊时间复杂度( amortized time complexity )

最好、最坏时间复杂度

不同情况下,时间复杂度不一样。

最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度。

最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。

平均时间复杂度

加权平均值,也叫作期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

只有同一块代码在不同的情况下,时间复杂度有量级的差距,我们才会使用这三种复杂度表示法来区分。

均摊时间复杂度

均摊时间复杂度,以及它对应的分析方法,摊还分析(或者叫平摊分析)

摊还分析法,通过摊还分析得到的时间复杂度我们起了一个名字,叫均摊时间复杂度。

运行的时序关系,将这一组操作放在一起分析,然后试着将高耗时的分配到低耗时的操作。

在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

均摊时间复杂度就是一种特殊的平均时间复杂度

你最应该掌握的是它的分析方法,摊还分析。