记账方法

概述

记账方法（Accounting Method）又称银行家方法（Banker’s Method），为不同操作分配不同的摊还代价，当摊还代价超过实际代价时，差额作为信用（credit）存储在数据结构中的特定对象上；当实际代价超过摊还代价时，消费之前积累的信用来支付差额。关键约束是总信用永不为负。

定义

记账方法

对每个操作 $i$，分配摊还代价 ${\hat{c}}_i$，使得：

• 当 ${\hat{c}}_i>c_i$ 时，将差额 ${\hat{c}}_i-c_i$ 作为信用存储在数据结构的对象中
• 当 ${\hat{c}}_i<c_i$ 时，从已存储的信用中取出 $c_i-{\hat{c}}_i$ 来支付

关键约束：对于任何时刻，数据结构中存储的总信用 $\ge 0$。

则 $n$ 个操作的总代价满足： ${\sum }_{i=1}^n{c}_i\le {\sum }_{i=1}^n{\hat{c}}_i$

核心性质

1. 差异化摊还代价：与16.1 聚合分析不同，记账方法可以为不同类型的操作分配不同的摊还代价，使得分析更加精细和灵活。
2. 信用机制：信用存储在数据结构中的具体对象上（如栈中的元素、计数器的二进制位），而非整个数据结构。这是与16.3 势能方法的关键区别。
3. 总信用非负约束：必须始终保证 $\text{总信用}\ge 0$。如果某一时刻信用为负，说明摊还代价分配不足，分析失败。
4. 直观易懂：信用存储在具体对象上的机制非常直观，类似于”预付费”概念——提前多付的钱存起来，以后需要时使用。

经典例子

栈操作

对三种栈操作分配如下摊还代价：

操作	实际代价	摊还代价	信用变化
PUSH(S, x)	1	2	+1（存储在被压入的元素上）
POP(S)	1	0	-1（消费栈顶元素的信用）
MULTIPOP(S, k)	$\min (k,\Vert S\Vert )$	0	消费每个弹出元素的信用

验证：每个被压入的元素携带 $1$ 单位信用。POP 或 MULTIPOP 弹出元素时，恰好消费其携带的信用。因为只能弹出已被压入的元素，所以信用永远不会为负。

$n$ 个操作的总摊还代价 $\le 2n=O(n)$，每个操作摊还 $O(1)$。

二进制计数器

对 INCREMENT 操作中翻转的每一位分配摊还代价：

翻转类型	实际代价	摊还代价	信用变化
$0\to 1$（置位）	1	2	+1（存储在该位上）
$1\to 0$（复位）	1	0	-1（消费该位的信用）

验证：每次将某位从 $0$ 翻转为 $1$ 时，存入 $1$ 单位信用。该位将来被翻回 $0$ 时，恰好消费这 $1$ 单位信用。因为只有被置为 $1$ 的位才会被翻回 $0$，所以信用始终非负。

$n$ 次 INCREMENT 的总摊还代价 $\le 2n=O(n)$，每次操作摊还 $O(1)$。

与聚合分析的区别

维度	聚合分析	记账方法
摊还代价	所有操作相同	不同操作可不同
分析粒度	序列整体	单个操作
灵活性	低	中
直观性	高（直接求和）	高（信用机制）
适用场景	操作类型单一	操作类型多样

参见

• 摊还分析 — 记账方法所属的总体分析框架
• 16.1 聚合分析 — 更简单但灵活性较低的摊还方法
• 16.3 势能方法 — 将信用提升为全局势能函数的方法
• 16.4 动态表 — 记账方法的应用案例之一