[TIL#3] Amortized Time?

Amortized Timeとは?
平均時間は時間複雑度を表す方法であり、アルゴリズムは1回だけ非常に悪い時間複雑度を有するが、通常は異なる時間複雑度を有する場合に用いられる.例えば、ArrayListは、動的に長くなるデータ構造であってもよい.
ArrayListとResized Array

ArrayList<String> merge(String[] words, String[] more) {
	ArrayList<String> sentence = new ArrayList<String>();
    
    for(String w: words) sentnece.add(w);
    for(String w: more) sentence.add(w);
    return sentence;
}

デフォルトでは、Javaのような言語は配列の長さを制限します.arrayのサイズはarrayの作成時に決定されます.長さのデータ構造を動的に調整する必要がある場合は、ArrayListを使用します.ArrayListは必要に応じて寸法を再調整することができるが、O(1)時間が必要である.
nサイズの配列があるとします.次に、各要素の容量が増加したときにコピーする要素を逆に計算できます.kの要素を追加するたびにarrayのサイズは前の半分になります.したがって、k/2をコピーする必要があります.

    final capacity increase: n/2 elements to coply
    previous capacity increase : n/4 elements to copy
    previous capacity increase : n/4 elements to copy
    previous capacity increase : n/4 elements to copy
    ...
    second capacity increase : 2 elements to copy
    first capacity increase: 1 element to copy

したがって、Nに要素を追加する合計は、N/2+N/4...+2+1.これはNより約小さい.
このような過程が明確であれば、約1キロ離れた店を考えてみましょう.0.5キロ歩いて0.25キロ歩いて0.125キロ・・・繰り返し続けると、絶対に1キロを超えません(もちろん収束します)