상각 분석(Amortized Analysis)이란?
상각 분석은 가끔 발생하는 연산은 매우 느리지만, 빈번하게 실행되는 대부분의 연산은 빠른 경우에 사용하는 비용 분석 기법입니다. 해시 테이블(Hash Table), 분리 집합(Disjoint Set) 등의 자료 구조 성능을 평가할 때 상각 분석이 반드시 필요합니다.
해시 테이블에서는 대부분의 경우 탐색 시간 복잡도가 O(1)로 상수 시간이 소요되지만, 때때로 O(n) 연산이 실행되기도 합니다. 해시 테이블에서 원소를 검색하거나 삽입할 때 일반적으로는 상수 시간 안에 작업이 완료되지만, 충돌(Collision)이 발생하면 충돌 해결을 위해 O(n) 시간의 연산이 추가로 필요할 수 있습니다.
집계 방법(Aggregate Method)
집계 방법은 연산 시퀀스의 전체 총비용(total cost)을 구하는 데 사용됩니다. 대량의 데이터를 한꺼번에 추가할 때 다음 공식을 통해 상각 비용(amortized cost)을 계산할 수 있습니다.
n개의 연산으로 이루어진 시퀀스의 비용은 다음과 같습니다.
$\frac{Cost ( n\:operations)}{n}=\frac{Cost (normal\:operations)+Cost (Expensive\:operations)}{n}$
상각 분석 예제: 동적 배열
동적 배열(Dynamic Array)에서는 지정된 인덱스에 항목을 O(1) 시간에 삽입할 수 있습니다. 하지만 해당 인덱스가 배열에 존재하지 않으면 상수 시간 내에 작업을 수행할 수 없습니다. 이런 경우에는 먼저 배열의 크기를 두 배로 확장한 후, 인덱스가 존재하면 요소를 삽입합니다.
동적 배열에서 ci를 i번째 삽입 연산의 비용이라고 정의하겠습니다.
$So\:ci=1+\begin{cases}i\:-\:1,if\:i-1\:is\:power\:of\:2 \\0, \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:Otherwise\end{cases}$
$$\frac{\displaystyle\sum\limits_{i=1}^n ci}{n}\leq\frac{n+\displaystyle\sum\limits_{j=1}^{\lfloor\log{2}{\lgroup n-1\rgroup}\rfloor} 2j}{n}=\frac{O\lgroup n\rgroup}{n}$$
위 식에서 알 수 있듯이, 동적 배열에 대한 n번의 삽입 연산 전체 비용을 n으로 나누면 결국 O(1)의 상각 비용을 얻을 수 있습니다. 즉, 가끔 발생하는 비용이 큰 배열 재할당 연산을 모든 연산에 균등하게 분배하면, 각 삽입 연산은 사실상 상수 시간에 수행된다고 볼 수 있는 것입니다.