gpt-5.6-terra が作成
ある 1 回の操作だけを見ると、通常より多くの仕事をすることがある。
償却計算量では、各操作を個別に上から抑える代わりに、操作列全体の仕事量を抑える。
ポテンシャルは、データ構造の各状態に定める、将来の重い処理に充てられる貯金を表す非負の数である。
ポテンシャルが増える操作では、実際の計算量に貯金の積立額を上乗せして記帳する。
重い処理が起きてポテンシャルが減るときは、その貯金を取り崩して計算量を支払う。
全体で $T$ 回の操作を行うとする。
$t$ 番目の操作の実際の計算量を $c_t$、その操作後のポテンシャルを $\Phi_t$ とする。
操作 $t$ の償却コストを $\hat{c}t=c_t+\Phi_t-\Phi{t-1}$ と定める。
操作列全体では、ポテンシャルの途中の増減が相殺される。
したがって、$\sum_{t=1}^T c_t=\sum_{t=1}^T \hat{c}t-\Phi_T+\Phi_0\le\sum{t=1}^T \hat{c}_t+\Phi_0$ が成り立つ。
この不等式では、ポテンシャルが常に非負であることを使った。
ポテンシャルは、実装に保持する値ではない。
解析のために定める帳簿上の数である。
したがって、償却コストの総和と初期ポテンシャルがともに $O(f)$ なら、実際の総計算量も $O(f)$ である。
配列 $A$ に対して次の操作を行いたい。
range_chmin(l, r, x) $A_i \leftarrow \min(A_i,x) \quad (l \le i < r)$range_sum(l, r) $\sum_{i=l}^{r-1} A_i$