상각 분석(Amortized Analysis)이란?
상각 분석은 일련의 연산(sequence of operations) 전체를 대상으로 평균적으로 소요되는 실행 시간을 구하는 기법입니다. 흔히 알고리즘의 '평균 경우 분석(average-case analysis)'과 혼동하기 쉽지만, 상각 분석은 항상 평균적인 입력만을 가정하지 않습니다. 오히려 최악의 경우(worst-case)가 발생하는 상황도 고려 대상에 포함됩니다.
즉, 상각 분석은 일련의 여러 연산에 대해 최악의 경우를 기준으로 평균 비용을 계산하는 방법이라고 이해할 수 있습니다. 개별 연산마다 비용이 서로 다르고, 특정 연산은 비용이 매우 높게 발생할 때 유용합니다. 이번 글에서는 가장 대표적인 예제인 이진 카운터(binary counter)를 통해 상각 분석의 개념을 살펴보겠습니다.
k비트 이진 카운터의 동작 원리
k비트 이진 카운터는 길이가 k인 이진 배열로 구현하며, 초기값은 모두 0입니다. 이 값에 대해 증가(increment) 연산을 여러 번 수행하게 됩니다.
8비트 배열이 증가 연산을 거치며 변화하는 과정은 다음과 같습니다.
00000000 → 00000001 → 00000010 → 00000011 → 00000100 → 00000101 → … → 11111111
증가 연산의 핵심 로직은 단순합니다. 숫자의 마지막 비트부터 거꾸로 탐색하여 처음 만나는 0을 찾아 1로 바꾸고, 그 앞에 있던 연속된 1들은 모두 0으로 바꾸는 것입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int main(){
int number[] = {1,0,0,1,0,1,1,1};
int length = 8;
int i = length - 1;
// 뒤에서부터 연속된 1을 모두 0으로 변경
while (number[i] == 1) {
number[i] = 0;
i--;
}
// 처음 만난 0을 1로 변경
if (i >= 0)
number[i] = 1;
for(int i = 0 ; i<length ; i++)
cout<<number[i]<<" ";
}
실행 결과
1 0 0 1 0 0 0 0
입력 {1,0,0,1,0,1,1,1}에 증가 연산을 한 번 적용하면, 뒤의 세 비트 111이 000으로 바뀌고 그 앞의 0이 1로 바뀌어 {1,0,0,1,0,0,0,0}이 출력됩니다.
상각 분석을 통한 비용 계산
개별 증가 연산 하나의 비용은 그때그때 다르지만, 최악의 경우에는 모든 비트를 뒤집어야 하므로 비트 수에 비례하는 비용이 듭니다. 그렇다면 n번의 연산을 수행했을 때 총비용은 얼마나 될까요?
n번의 연산 과정에서 발생하는 비트 반전(flip)의 총 횟수는 다음과 같습니다.
n + n/2 + n/4 + … + n/k²
- n번의 연산 중 절반(n/2번)은 첫 번째 비트만 반전합니다.
- 4분의 1(n/4번)은 두 번째 비트까지 반전합니다.
- 이런 식으로 점점 더 적은 횟수의 연산만 많은 비트를 반전하게 됩니다.
이 수열은 공비가 1/2인 등비수열(GP)이므로, 무한급수의 합 공식을 적용하면 다음과 같이 상한을 구할 수 있습니다.
Sum = n + n/2 + n/4 + … < n/(1 − 1/2) = 2n
따라서 n번의 연산에 필요한 총비용은 최대 2n이며, 이를 연산 횟수 n으로 나누면 연산당 상각 비용(amortized cost)은 다음과 같습니다.
상각 비용 = 2n / n = O(1)
결론
증가 연산 하나하나를 개별적으로 보면 최악의 경우 O(k)의 비용이 들지만, 상각 분석 관점에서 보면 연산당 평균 비용은 O(1), 즉 상수 시간입니다. 이는 비트 수 n에 비례하지 않는다는 의미로, 이진 카운터의 증가 연산이 실제로 매우 효율적임을 보여주는 대표적인 상각 분석 사례입니다.