償却解析
Java における ArrayList のような、より多くの要素が追加されるようなサイズで大きくなる動的配列を考える。サイズ 4 の動的配列で始めた場合、それに 4 つの要素を push するのに定数時間かかるだろう。しかし、それに 5 つ目の要素を push することは、現在のサイズの 2 倍 (8) の新しい配列を作成し、古い要素を新しい配列にコピーし、さらに新しい要素を追加するので、より長い時間がかかるだろう。次の 3 つの push 操作は、同様に定数時間かかる。そして次の追加は配列サイズの遅い 2 倍化を必要とするだろう。 一般に、サイズ n の配列に n + 1 回の push を行うことを考えたとき、最後の 1 回以外は定数時間かかり、最後の 1 回はサイズの 2 倍化を行うのに O(n) かかることに気づく。全部で n + 1 回の操作があったので、これの平均を取り、動的配列への要素の push が O ( n + 1 n ) = O ( 1 ) {\displaystyle O({\tfrac {n+1}{n}})=O(1)} の定数時間かかることがわかる。