算法设计与分析6.ppt

* * Chapter 6 Amortized Analysis 平摊分析基本思想 ? 在平摊分析中执行一系列数据结构操作所需要时间是通过对执行的所有操作求平均而得出的 平摊分析可用来证明在一系列操作中即使单一的操作具有较大的代价通过对所有操作求平均后平均代价还是很小的. 平摊分析与平均情况分析不同, 不牵涉到概率 Chapter 6 Amortized Analysis 平摊分析的方法 聚集方法