【算法】平摊分析

平摊分析种类

1），聚集分析：n个操作所构成的序列的总时间在最坏情况下为T(n) 平摊代价为：T(n)/n

2），记账法:平摊代价高的操作，当做存储，用来补偿平摊代价低得操作。

3），势能法：平摊代价=实际代价+i点的势能-（i-1）点的势能

平摊分析总结

平摊分析可用来证明在一系列操作中，即使单一的操作具有较大的代价，通过对所有操作求平均后，平均代价还是很小的。平摊分析与平均情况分析的不同之处在于它不牵涉到概率。这种分析保证了在最坏情况下每个操作具有平均性能。