摊还分析概述
摊还分析（Amortized Analysis）是一种分析算法序列平均代价的方法，它关注的是在一系列操作中，每个操作的平均代价（摊还代价），而非最坏情况下的单次操作代价。
应用场景
当算法中某些操作代价较高，但大多数操作代价较低时，摊还分析能够给出更真实的平均性能评估。
核心思想
对 n 个操作进行整体性分析，将总代价分摊到每个操作上，得到每次操作的平均摊还代价。即使某些操作代价很高，如果它们发生频率很低，摊还代价仍然可能是较小的。
三种主要方法
- 聚合分析 — 直接对整体求平均
- 核算法 — 为廉价操作”预存”信用
- 势能法 — 定义势能函数衡量系统状态
