상각 분석(Amortized Analysis)이란?
상각 분석(분할상환 분석)은 드물게 아주 느리게 수행되는 연산이 있지만, 대부분 자주 실행되는 연산은 빠르게 처리되는 경우에 사용하는 알고리즘 분석 기법입니다. 단일 연산의 최악의 경우만 보는 대신, 긴 연산 열 전체에 걸쳐 비용을 평균 내어 실질적인 성능을 평가합니다.
상각 분석이 필요한 대표적인 자료구조
상각 분석은 해시 테이블(Hash Table), 서로소 집합(Disjoint Set), 동적 배열 등에서 활용됩니다.
해시 테이블을 예로 들면, 대부분의 경우 탐색 및 삽입 연산은 O(1)의 상수 시간에 완료됩니다. 하지만 해시 충돌(collision)이 발생하면 충돌을 해결하기 위해 최악의 경우 O(n) 시간의 연산이 필요할 수 있습니다. 즉, 평균적으로는 상수 시간에 작업이 수행되지만 특정 순간에는 선형 시간이 소요되는 것인데, 이러한 불균형한 비용 분포를 분석할 때 상각 분석이 유용합니다.
집계 방법(Aggregate Method)
집계 방법은 일련의 연산 전체에 대한 총 비용 T(n)을 구한 뒤, 이를 연산 횟수 n으로 나누어 평균 비용, 즉 상각 비용(amortized cost)을 계산하는 가장 직관적인 방법입니다.
n개의 연산으로 이루어진 연속열에 대해 상각 비용은 다음과 같이 정의됩니다.
상각 비용 = T(n) / n (단, T(n)은 n개 연산의 총 비용)
모든 n에 대해 이 값이 일정한 상한을 넘지 않으면, 해당 연산열의 상각 비용은 그 상한으로 볼 수 있습니다.
상각 분석 예제: 동적 배열(Dynamic Array)
동적 배열에서는 삽입하려는 인덱스가 유효한 범위 내에 있을 때 해당 위치에 원소를 O(1) 시간에 삽입할 수 있습니다. 하지만 배열이 이미 가득 차 있다면 상수 시간 안에 작업을 마칠 수 없습니다. 이 경우 배열의 크기를 먼저 두 배로 확장한 뒤 원소를 삽입하게 됩니다.
동적 배열에서 ci를 i번째 삽입 연산의 비용이라고 하면 다음과 같이 나타낼 수 있습니다.
- 배열에 여유 공간이 있는 경우: ci = 1 (원소 하나만 삽입)
- 배열이 가득 차 크기를 두 배로 늘려야 하는 경우: ci = i (기존 i−1개 원소를 새 배열로 복사 + 새 원소 1개 삽입)
n번의 삽입에 대한 총 비용 T(n)을 계산해 보면, 크기 조정(resizing)은 배열 크기가 1, 2, 4, 8, … 과 같이 2의 거듭제곱을 넘어설 때만 발생하므로, 총 복사 비용은 n보다 작은 2의 거듭제곱들의 합, 즉 n − 1 이하입니다. 따라서 다음 부등식이 성립합니다.
T(n) ≤ n + (n − 1) < 3n
이를 n으로 나누면 상각 비용은 다음과 같습니다.
T(n) / n < 3 = O(1)
즉, 가끔 발생하는 비싼 재할당 연산 비용을 모든 삽입 연산에 걸쳐 '분할상환'하더라도, 각 삽입 연산의 평균 비용은 여전히 상수 시간임을 알 수 있습니다. 이것이 바로 상각 분석의 핵심 아이디어입니다.
마치며: 다른 상각 분석 기법들
집계 방법 외에도 상각 분석에는 회계 방법(Accounting Method)과 잠재력 방법(Potential Method)이 있습니다. 회계 방법은 연산마다 미리 정해진 '수수료'를 적립해 두었다가 비싼 연산이 발생할 때 사용하는 방식이고, 잠재력 방법은 자료구조의 상태를 나타내는 잠재 함수를 정의하여 비용 변화를 추적하는 방식입니다. 세 가지 기법 모두 결국 동일한 목표, 즉 연산열 전체의 평균 성능을 엄밀하게 증명하는 것을 지향합니다.