ArrayStack

配列みたいな。比較的シンプル

get(i) … i番目の要素を返す

set(i,x) … i番目の要素をxに置き換える

add(i,x) … i番目にxを追加する

remove(i) … i番目の要素を削除する

getとsetはO(1)。addとremoveは、例えば真ん中辺りをremoveしたら消した所を埋めるためにそれ以降のデータを1つずつスライドしないといけないので、要素数をnとしたときO(n-i)になる。

resize()

要素数が配列aからはみ出そうor要素少なすぎてスペースめちゃ余ってる…というときは、resize()が実行されて配列のサイズが2nに調整される。

新しいサイズの配列bを作って、中身をコピーして、乗り換える。O(n)

https://gyazo.com/64115467251a77a21e392ce7ac9e5e29

n+1 >= a.length() または n*3 <= a.lengthのとき、resizeして2nのサイズに調整する

毎回resize()してたらm回後ろに追加するのにもO(m^2)回かかってしまう（1つ後ろに追加するごとに毎回作り直さないと行けないので）

償却解析をする

1回以上、m回add(i,x)やremove(i)をしたときのresize()の合計実行時間はO(m)である.

まず「resizeを呼んだとき要素数がnだったとすると、前回のresizeから少なくともn/2 - 1回以上addとかremoveをしてるよ」を証明する。「少なくとも」なので

add→add→…→add→resize

remove→remove→…→remove→resize

みたいな最短の2通りについてn/2 - 1回以上かかることをいえばよい。

addのみで満タンになったとき

前回：■■■■■■■■□□□□□□□□

今回：■■■■■■■■■■■■■■■■ (要素数n)

n/2 回以上追加していることが分かる。

removeのみでスペースが余ったとき

前回：■■■■■■□□□□□□

今回：■■■■□□□□□□□□

n/2 - 1回以上追加していることが分かる

ここの -1 はn=0,length=1のときのコーナーケース回避用なので実質n/2と考えていい

まあこれを使って変形で証明ができる。

時間が足りない人に厳密でない説明を書いておく。自分用。

厳密でない証明

removeをm回繰り返していくときのresizeの合計実行時間(＝要素のコピー回数の合計)よりも、addをm回繰り返していくときのresizeの合計実行時間(＝要素のコピー回数の合計)の方が長そう、ということがなんとなく分かる(要素数が増えていくにつれてresizeも時間がかかってくるので)。なのでaddのときだけを考える。

addを何回も繰り返して満タン状態(状態A)になったときの「これまでの合計コピー回数」を考える。

■■■■■■■■ ■■■■■■■■ ■■■■■■■■ ■■■■■■■■ (状態A、要素数n = 32 = addした回数m)

前回のresizeでは、16個をコピーして新しい配列に乗り換えて状態Bになっていることがわかる。つまり

■■■■■■■■ ■■■■■■■■ □□□□□□□□ □□□□□□□□ (状態B、前回のresize後)

こんな感じ。状態Aになったときの要素数をn、addした回数をmとするとn = mが成立する。

前回のresizeのコピー回数はn/2回。ちなみに前々回はn/4回。さらにその前はn/8回。これらのコピー回数をすべて足すとn-1になる。(2進数で考えるとわかりやすい、n=100000(2進数)のとき、コピー合計は11111になる)