核算法

核算法(Accounting Method)是摊还分析的一种方法,通过对不同操作分配不同的摊还代价来实现分析。

基本思想

为每种操作分配一个”摊还代价”,当实际代价低于摊还代价时,差额作为”信用”存储起来;当实际代价高于摊还代价时,使用之前存储的信用来支付差额。

核心规则

  • 信用余额必须始终非负(保证摊还代价是实际代价的上界) -总摊还代价 总实际代价

核算法相比于聚合分析更灵活,允许为不同类型的操作分配不同的摊还代价。

链接到