상각 분석(Amortized Analysis)이란?
상각 분석은 일련의 연산 전체를 놓고 평균적인 비용을 계산하는 알고리즘 분석 기법입니다. 어떤 자료구조는 대부분의 연산이 매우 빠르게 수행되지만, 아주 가끔 발생하는 특정 연산만 유난히 느릴 수 있습니다. 이럴 때 최악의 경우만 보는 일반적인 시간 복잡도 분석보다, 여러 번의 연산에 걸쳐 비용을 '나누어 안분'하는 상각 분석이 더 현실적인 성능을 보여줍니다.
대표적으로 해시 테이블(Hash Table), 서로소 집합(Disjoint Set), 동적 배열(Dynamic Array) 등의 자료구조 성능을 평가할 때 상각 분석이 필수적으로 활용됩니다.
해시 테이블에서의 상각 분석
해시 테이블에서 원소를 검색하거나 삽입하는 작업은 대부분의 경우 상수 시간, 즉 O(1)의 시간 복잡도로 처리됩니다. 하지만 두 개 이상의 데이터가 같은 해시 값(버킷)에 저장되는 충돌(Collision)이 발생하면, 충돌을 해결하기 위해 선형 탐색 등 추가 작업이 필요해 최악의 경우 O(n)의 시간이 소요될 수 있습니다.
즉, 해시 테이블은 '평소에는 빠르고, 가끔 느린' 자료구조입니다. 따라서 단순히 최악의 경우 O(n)이라고 결론 내기보다는, 충돌이 드물게 발생한다는 점을 고려한 상각 분석으로 전체적인 평균 성능을 평가하는 것이 합리적입니다.
집계 방법(Aggregate Method)
집계 방법은 상각 분석의 가장 기본적인 접근 방식으로, n개의 연산 시퀀스 전체에 드는 총 비용 T(n)을 구한 뒤, 이를 연산 횟수로 나누어 상각 비용을 계산합니다.
공식으로 표현하면 다음과 같습니다.
상각 비용 = T(n) / n
예를 들어, 대량의 데이터를 순차적으로 삽입하는 상황이라면 전체 삽입 작업에 걸린 총비용을 구하고, 그 값을 삽입 횟수 n으로 나누면 한 번의 삽입에 대한 평균 상각 비용을 얻을 수 있습니다.
예제: 동적 배열(Dynamic Array)의 삽입
동적 배열은 상각 분석을 설명할 때 가장 널리 쓰이는 예제입니다. 동적 배열에서는 인덱스가 지정된 위치에 원소를 O(1) 시간에 삽입할 수 있습니다. 하지만 해당 인덱스가 현재 배열 범위를 벗어나거나 배열이 이미 가득 찬 경우에는 상수 시간 안에 작업을 완료할 수 없습니다.
이런 경우 동적 배열은 다음과 같이 동작합니다.
- 현재 배열 크기를 두 배(2배)로 확장합니다.
- 기존 원소들을 새 배열로 모두 복사합니다.
- 그 후에야 새 원소를 삽입합니다.
배열 확장 및 복사 작업은 기존 원소 수에 비례하여 O(n)의 시간이 걸립니다. 문제는 이런 확장이 자주 일어나지 않는다는 점입니다. 크기가 두 배씩 커지기 때문에, 확장 간격은 점점 더 멀어집니다.
삽입 비용의 수학적 분석
i번째 삽입의 비용을 ci라고 정의해 봅시다.
- 배열에 공간이 남아 있는 경우: ci = 1
- 배열이 가득 차서 확장이 필요한 경우(i-1이 2의 거듭제곱일 때): ci = i
n번의 삽입 전체에 대한 총비용을 계산하면, 일반적인 삽입 비용(각 1)의 합 n에 더해, 확장 시 발생하는 비용(2의 거듭제곱들의 합)이 추가됩니다. 2의 거듭제곱들의 합은 n보다 작으므로, 전체 총비용은 3n 미만, 즉 O(n)으로 bounded 됩니다.
따라서 한 번의 삽입에 대한 상각 비용은 다음과 같습니다.
T(n) / n < 3n / n = O(1)
결론적으로, 동적 배열에 원소를 삽입하는 연산은 최악의 경우 O(n)이지만, 상각 분석 관점에서는 O(1)의 시간 복잡도를 가진다고 말할 수 있습니다. 이것이 바로 상각 분석이 실제 자료구조 성능을 더 정확하게 반영하는 이유입니다.
정리
- 상각 분석은 연산 시퀀스 전체의 평균 비용을 구하는 분석 기법이다.
- 해시 테이블처럼 평소엔 빠르지만 가끔 느린 연산이 섞인 자료구조 분석에 적합하다.
- 집계 방법은 총비용 T(n)을 연산 횟수 n으로 나누어 상각 비용을 계산한다.
- 동적 배열의 삽입은 최악 O(n)이지만 상각 비용은 O(1)이다.