平摊分析，又称摊还分析、-{zh-cn:均摊分析;zh-tw:平攤分析}-（）是計算機科學中的一种算法分析方法，常用於分析資料結構（特别是動態的資料結構）的复杂性。
对于某些数据结构来说，其操作在某些情况下需要耗费相当大的运算资源，但大部分时候开销显著小于最坏情况。如果只使用最坏情况分析，可能会错误地低估其在实际使用时的效率。由于输入的类型、长度等因素都可能影响某一操作的开销，平摊分析通过考虑一组包含了各种不同操作的序列，将少数开销较大的操作平摊至整个序列上，从而得出一个更贴合算法实际应用时的复杂度。
应注意平摊分析與或概率算法分析的不同。平均时间分析中，平均化的是所有可能的输入；在概率算法的概率分析中，平均化的是所有可能的随机选择；而在平摊分析中，平均化的是一系列操作的耗费。平摊分析假设的是最坏情况输入并且通常不运行随机选择。
历史
1985年，美国计算机科学家罗伯特·塔扬首先在他的论文中提出了聚集法（现已归为平摊分析中的一种方法）。他在文章中指出，有必要开发一种比一般概率分析更实用的分析方法。
使用記帳法证明
我們规定，为、、的分别发放2、0、0个积分，如下表所示
我们需要证明对于任意n长度的操作序列，其存款数永远为非负，即：
\sum_{k=1}^n \hat{c_i} \ge \sum_{k=1}^n c_i
注意到，每个元素在压入堆栈时获得2积分，本次操作消耗1积分的同时存入1积分，因此不论通过何种方法弹出时，一定可以取出压入时存入的1积分，因此存款始终为非负。
至此，可以证明在多重弹出堆疊上的任意n长度的操作序列的平攤成本為 O(1)。
使用位能法证明
我們定義位能函數 \Phi(D_i) 為執行i個操作後，堆疊內的元素個數。显然， \Phi(D_i) 是非负的：
: \Phi(D_0)=0 ，因為堆疊一開始是空的
: \Phi(D_i)\ge 0 ，因為堆疊的元素個數一定 \ge 0
計算堆疊S每一個操作的平攤成本。假设 S 在状态 \Phi(D_i) 时有 \left\vert S\right\vert 个元素：
可见每个操作的平攤成本都是 O(1) ，因此任意n长度的操作序列的平攤成本就是 O(1)。
或者，我們可以收取將任何項目從輸入數組複製到輸出數組的成本，以及該項目的早期排隊操作。 該計費方案將入隊的攤還時間加倍，但將出列的攤還時間減少到。
通常用法
- 在常见场合，我们把能很好平摊分析的算法称为“平摊算法”。
- 在线算法通常使用平摊分析。
参考资料
评论 (0)