動的arrayEdit
javaのarraylistまたはc++のstd::vector。 サイズ4の動的配列から始めた場合、4つの要素をその上にプッシュすることができ、各操作には一定の時間がかかります。 しかし、5番目の要素をその配列にプッシュすると、配列が現在のサイズ（8）の2倍の新しい配列を作成し、古い要素を新しい配列にコピーしてから、新し 次の3つのプッシュ操作も同様に一定の時間がかかり、その後の追加では配列サイズの倍加がさらに遅くなります。
一般に、サイズnの配列への任意の数のプッシュn+1を考えると、プッシュ操作はΛ(n){\displaystyle\Theta(n)}
サイズ倍増操作を実行するのに時間がかかる最後のものを除いて一定の時間がかかることに気付く。 合計n+1の操作があったので、これの平均を取ることができ、要素を動的配列にプッシュするには次のようになります: n Θ(1)+Θ(n)n+1=Θ(1){\displaystyle{\tfrac{n\Theta(1)+\Theta(n)}{n+1}}=\Theta(1)}
、一定の時間。
QueueEdit
示されているキューのRuby実装、FIFOデータ構造です。
class Queue def initialize @input = @output = end def enqueue(element) @input << element end def dequeue if @output.empty? while @input.any? @output << @input.pop end end @output.pop endend
エンキュー操作は、要素を入力配列にプッシュするだけです。
しかし、dequeue操作はより複雑です。 それ以外の場合、dequeueはO(n){\displaystyle O(n)}
入力配列から出力配列にすべての要素を追加する時間を取ります。nは入力配列の現在の長さです。 入力からn個の要素をコピーした後、出力配列が再び空になる前に、それぞれが一定の時間を要するn個のデキュー操作を実行できます。 したがって、O(n){\displaystyle O(n)}
時間だけでn個のdequeue操作のシーケンスを実行することができ、これは各dequeue操作の償却時間がO(1){\displaystyle O(1)}
