平摊分析 平攤分析英語Amortized analysis在计算机科学中是用於算法分析中的方法平攤分析常用於分析資料結構動態的資料結構在使用平攤分析前須知道資料結構各種操作所可能發生的時間並計算出最壞情况下的操作情況並加以平均得到操作的平均耗费时間平摊分析只能確保最坏情况性能的每次操作耗费的平均时间並不能確認平均情况性能 一個簡單的例子一個長度為 n displaystyle n 的list在list的最後要加入一筆新的資料此時要花費的操作時間為 O  n  displaystyle On 此時也是加入新的資料的最糟糕的情況但是一个 n displaystyle n 个插入的操作序列仍然可以在 O  n  displaystyle On 的时间内完成因为剩下的插入可以在常数时间内完成因此 n displaystyle n 个插入可以在 O  n  displaystyle On 的时间内完成因此每操作的平摊耗费为 O  n   n  O    displaystyle OnnO  注意平摊分析与平均时间分析和概率算法的概率分析不同在平均时间分析中我们平均化所有可能的输入在概率算法的概率分析中我们平均化所有可能的随机选择在平摊分析中我们平均化一系列操作的耗费平摊分析假设的是最坏情况输入并且通常不运行随机选择 平摊分析中几种常用的技术 聚合分析决定 n displaystyle n 个操作序列的耗费上界 T  n  displaystyle Tn 然后计算平均耗费为 T  n   n displaystyle Tnn  记账方法确定每个操作的耗费结合它的直接执行时间及它在对运行时中未来操作的影响通常来说许多短操作增量累加成债而通过减少长操作的次数来偿还 势能方法类似记账方法但通过预先储蓄势能而在需要的时候释放