ポテンシャル法

補題 8.1（「基本的なデータ構造」§8）・ ✓公理まで証明済み

データ構造の状態の列 $D_0, D_1, \ldots, D_m$ （ $D_0$ は初期状態、 $D_i$ は $i$ 番目の操作の直後の状態）と、 $i$ 番目の操作の実コスト $c_i$ が与えられているとする。状態の集合上の実数値関数 $\Phi$ が

\Phi(D_i) \ge \Phi(D_0) \qquad (i = 0, 1, \ldots, m)

を満たすとする。償却コストを $\hat{c}_i := c_i + \Phi(D_i) - \Phi(D_{i-1})$ で定めると

\sum_{i=1}^{m} c_i = \sum_{i=1}^{m} \hat{c}_i + \Phi(D_0) - \Phi(D_m) \le \sum_{i=1}^{m} \hat{c}_i

が成り立つ。とくに、ある定数 $a$ がすべての $i$ について $\hat{c}_i \le a$ を満たすならば、 $m$ 回の操作の総コストは $am$ 以下である。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

証明は Rikai の他の定理を参照していません（定義と論理だけで示されています）。