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

2019/04/01 posted in  极客-数据结构与算法之美
  • 最好情况时间复杂度(best case time complexity)
  • 最坏情况时间复杂度(worst case time complexity)
  • 平均情况时间复杂度(average case time complexity)
  • 均摊时间复杂度(amortized time complexity)

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

平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度,这个值是概率论中的加权平均值,也叫作期望值

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

大部分情况下,我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到,而均摊时间复杂度应用的场景比它更加特殊、更加有限。