動的配列の償却計算量

次の規則で末尾追加 $\mathrm{push}$ を実現するデータ構造を考える。容量 $c$ の配列 $A$ と現在の要素数 $n$（$0 \le n \le c$）を保持し、初期状態を $n = 0$、$c = 1$ とする。$\mathrm{push}(x)$ は次のように動作する。

• $n < c$ ならば $A[n] \leftarrow x$ とし、$n \leftarrow n + 1$ とする。
• $n = c$ ならば、まず長さ $2c$ の配列を新たに確保して既存の $c$ 個の要素をそこへ移し、$c \leftarrow 2c$ としてから上の操作を行う。

このとき、空の状態から $\mathrm{push}$ を $n$ 回（$n \ge 1$）行うときの要素の書き込み回数の合計は $3n$ 未満である。したがって 1 回の $\mathrm{push}$ あたりの償却計算量は $O(1)$ である。ただし、個々の $\mathrm{push}$ の最悪計算量は $\Theta(n)$ である。