배열(리스트 등)을 처음 선언할 때 한번에 많은 양의 메모리를 할당하는 것은 상당히 비효율적일 수 있다. Array Doubling을 통해 처음에는 메모리를 적게 할당하고, 메모리가 다 찼을 때마다 늘리게 되면 메모리 사용을 보다 효율적으로 할 수 있다. Time Complexity의 Asymptotic Analysis와 마찬가지로 알고리즘의 수행 시간을 분석하는 기법이다.
Amortized Analysis(분할 상환 분석)는 주어진 알고리즘의 시간 복잡도나 프로그램을 수행하는데 소요되는 시간 또는 메모리 같은 자원 사용량을 분석하기 위해서 사용하는 기법으로, 여러 호출에 대한 평균 비용을 계산하는 것이다.
추가 설명
put(x)를 호출할 때마다 array를 늘릴 필요는 없다.
$\begin{aligned} \frac {\sum_{i=1}^{n} \text{cost of calling put for the }i^{th}\text{ time} } n = O(?) \end{aligned}$
연산을 수행하다가 배열이 다 찼을 때 해결할 수 있는 2가지 방법이 있다.