상각 분석 (Amortized Analysis)

한 줄 정의: 한 번의 연산이 아니라 여러 번의 연산 전체를 놓고 비용을 평균 내어, 가끔 비싸 보이는 연산도 길게 보면 평균 비용이 낮다는 것을 증명하는 분석 방법입니다.

쉽게 풀면

커피 쿠폰을 생각해 보세요. 커피 9잔은 제값을 내지만 10번째 잔은 무료라면, 낱개로 보면 어떤 날은 돈을 내고 어떤 날은 공짜지만, 10잔 전체를 놓고 평균을 내면 한 잔당 비용은 항상 일정하게 낮습니다. 상각 분석도 이와 같습니다. 배열에 원소를 하나씩 추가하다가 공간이 꽉 차면 배열 크기를 두 배로 늘리는 작업은 가끔 시간이 오래 걸리지만, 전체 삽입 횟수로 나누어 보면 삽입 한 번의 평균 비용은 여전히 매우 작다는 것을 보여줍니다.

왜 중요한가

자료구조나 알고리즘의 성능을 논할 때, 최악의 경우 하나만 보고 "느리다"고 단정하면 실제 사용 패턴을 지나치게 비관적으로 평가하게 됩니다. 상각 분석은 이런 오해를 바로잡아 자료구조 설계 논문이나 시스템 논문에서 제안한 알고리즘의 실질적인 효율성을 정직하게 증명하는 표준적인 도구로 쓰입니다. 특히 해시 테이블, 캐시, 분산 시스템의 재조정(rebalancing) 연산처럼 가끔 비용이 튀는 연산을 다룰 때, 상각 분석 없이는 성능 주장을 뒷받침하기 어렵습니다.

논문에서는 이렇게 쓰입니다

"동적 배열의 삽입 연산은 배열 크기를 두 배로 늘리는 경우 O(n)이 소요되지만, 상각 분석(amortized analysis)을 적용하면 삽입당 평균 시간 복잡도는 O(1)임을 보일 수 있다."

이 문장은 특정 한 번의 삽입만 놓고 보면 느릴 수 있지만, 처음부터 끝까지 이어지는 전체 삽입 과정을 놓고 계산하면 삽입 한 번에 드는 평균 비용은 상수 시간에 불과하다는 이론적 보장을 설명한 것입니다.

"해시 테이블이 부하율(load factor) 임계값을 초과하면 전체 원소를 새 테이블로 재해싱(rehashing)하는 비용이 발생하지만, 상각 분석을 통해 삽입 연산의 상각 비용은 O(1)으로 유지됨을 보인다."

재해싱처럼 가끔씩만 발생하는 값비싼 연산이 있더라도, 전체 삽입 횟수에 걸쳐 비용을 나누어 계산하면 평균적으로는 여전히 빠르다는 것을 보여주는 예문입니다.

"제안하는 분산 캐시 정책은 캐시 미스 시 항목을 재배치하는 오버헤드를 수반하지만, 상각 분석 결과 요청당 상각 비용은 상수 시간 이내로 유지됨을 증명하였다."

시스템 논문에서 상각 분석이 자료구조뿐 아니라 캐시 재배치나 부하 분산과 같은 운영 비용을 정당화하는 데에도 쓰인다는 것을 보여줍니다.

조금 더 깊게 보면

상각 분석을 증명하는 대표적인 방법으로는 총합 방법(aggregate method), 회계 방법(accounting method), 퍼텐셜 방법(potential method) 세 가지가 흔히 언급됩니다. 총합 방법은 전체 연산 횟수에 대한 총비용을 직접 계산해 나누는 방식이고, 회계 방법은 각 연산에 미리 '신용(credit)'을 부여해 비싼 연산의 비용을 저렴한 연산이 쌓아둔 신용으로 지불하는 방식입니다. 퍼텐셜 방법은 자료구조의 상태를 나타내는 퍼텐셜 함수를 정의해, 상태 변화에 따른 퍼텐셜 값의 증감으로 상각 비용을 계산하는 가장 일반적인 형태입니다. 논문에서 "potential function", "credit-based argument" 같은 표현이 등장하면 대체로 이 세 방법 중 하나를 적용하고 있다고 보면 됩니다.

주의할 점

상각 분석은 평균적인 실행 시간이라는 점에서 통계적인 '평균 사례 분석(average-case analysis)'과 혼동하기 쉽지만 전혀 다른 개념입니다. 평균 사례 분석은 입력이 무작위로 주어진다는 확률적 가정에 의존하는 반면, 상각 분석은 어떤 입력이 와도 항상 성립하는 결정론적 보장입니다. 유니온-파인드의 경로 압축 연산이 대표적인 상각 분석 적용 사례입니다.