Dynamic Arrays

通常の静的な配列と異なり、Dynamic Arrayは後から配列のサイズを増やすことができる。 Dynamaic Arrayは以下の操作を持つデータ構造である。

Get(i)：インデックスiの要素を返す
Set(i, val)：インデックスiの場所にvalをセット
PushBack(val)：valを配列の末尾にセット
Remove(i)：インデックスiの要素を削除する
Size()：要素の合計数を返す

Dynamic ArrayはC++ではvector, JavaではArrayList, pythonではlistなどで実装されている。

配列にpushbackを繰り返してサイズが一杯になった場合、新たに現在の配列のサイズの2倍のサイズの新しい空間をメモリに確保する。そして、現在の配列に入っている要素を新しい配列にコピーし、現在の配列をメモリから開放してから新しい配列にpushbackしていく。

各操作のオーダーは以下の通り。 f:id:rikeiin:20180407173703p:plain

Dynamic Arrayまとめ

静的な配列と異なり、Dynamic Arrayはサイズが変更できる
新しい要素の追加は基本的に定数時間だが、配列のリサイズが伴う場合はO(n)
確保したメモリ空間が無駄になることがある

Amortized Analysis

Amortized Analysisは償却解析、ならし解析とも呼ばれ、一回の実行で毎回最悪時間計算量を見積もるのではなく、一連の操作でどのくらいの計算量になるかを解析する手法である。例えば、上のDynamic Arrayの要素追加において時間計算量は基本O(1)だがリサイズが伴うとO(n)になるという話があった。こういったときに配列に連続して要素を追加していったときにトータルとして計算量がどのくらいになるかというのを見積もる。

ここで操作をn回連続して行ったときのAmortized costというものを導入し、以下のように計算される。

$\frac{\mathrm{Cost(}n \mathrm{\ operations)}}{n}$