Amortized Analysis - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

图解

详解

平摊分析概念以及知识点 平摊分析 关于平摊分析、表的扩增、势能分析初步理解

要点

• 定义：若k次操作的总开销<=kT(n)，则平摊开销是T(n)
  • 注意：平摊Amortized ≠ 平均Average，平摊分析时间与传统分析方法的平均情况下时间不同，它是最坏情况下的平均时间