償却解析
Ruby の キュー(FIFO)実装を見てみよう。
enqueue 操作では、単に入力配列に要素を push している。この操作は入力または出力の長さに依存せず、それゆえ定数時間で走る。 しかし、dequeue 操作はより複雑である。もし出力配列がすでになんらかの要素を持っていれば、それは定数時間で走る。そうでなければ、dequeue は入力配列から出力配列にすべての要素を追加するのに O(n) かかる。ここで、 n は入力配列の現在の長さである。入力から n 要素をコピーした後で、我々は出力配列が再び空になる前に n 回の dequeue 操作を行うことができる。その操作のそれぞれは定数時間かかる。このようにして、我々はわずか O(n) の時間で一連の n 回の dequeue 操作を行うことができる。これは、それぞれの dequeue 操作の償却された時間が O(1) であることを意味する。 あるいは、我々はそのアイテムに対する初期の enqueue 操作に対する、入力配列から出力配列への各アイテムのコピーのコストを請求することができる。この請求スキームは enqueue に対する償却時間を 2 倍にするが、dequeue に対する償却時間を O(1) に減少させる。