Amortized Analysis

1. Aggregate analysis
   a sequence of $n$ operations takes worst-case time $T(n)$ int total. In the worst-case, the average cost, or amortized cost, per operation is $T(n)/n$.

example: stack with MultiPop(int k, Stack S)

2. Accounting method
   When an operation’s amortized cost is $\hat{c_i}$ exceeds its actural cost $c_i$, we assign the dirrerence to specific objects in the data structure as credit. Credit can pay for the later operations whose amortized cost is less than their actual cost.
   实际成本优于均摊成本，把差额分配给数据结构中的特定对象，表示为 credit, credit 可以帮助支付后续操作的费用，这些操作的摊还成本小于实际成本
   For all sequences of $n$ operations, we must assure:

$$\sum_{i=1}^n \hat{c_i} \geq \sum_{i=1}^n c_i$$

• 当某次操作的 摊还代价 > 实际代价（(\hat {c}_i > c_i)），
  多出来的部分 (\hat {c}_i - c_i) 被存为 credit（信用），附着在数据结构的某些对象上。

• 当后续某次操作 实际代价 > 摊还代价（(c_j> \hat {c}_j)），
  就用之前存下的 credit 来 “支付” 超出的部分。

但有一个硬性约束：

任何时候都不能透支 credit！
也就是说，在任何前缀操作 (1…k) 中，累计的 credit 必须 ≥ 0。

这等价于要求：

$$\forall k,\quad \sum_{i=1}^k \hat{c}_i \geq \sum_{i=1}^k c_i$$

特别地，对整个序列（(k = n)）就有：

$$\sum_{i=1}^n \hat{c}_i \geq \sum_{i=1}^n c_i$$

不同操作的摊还代价可能会不同，

3. Potential method