분할 상환 분석

분할 상환 분석(amortized analysis)은 알고리즘의 연산이 반복될 때, 각 연산의 평균적 비용을 계산하여 알고리즘의 성능을 평가하는 방법이다. 이는 최악의 경우 시간 복잡도보다 더 현실적인 성능 평가를 제공하며, 연산 간 비용이 불균등한 자료구조에서 특히 유용하다.

개념

어떤 자료구조에서 일부 연산은 가끔 매우 높은 비용을 요구할 수 있지만, 전체 연산의 흐름에서 보면 대부분 저렴한 연산들이기 때문에, 총 수행 시간에 기반한 평균적 비용으로 각 연산의 효율을 판단한다.

• 총 수행 시간 T(n)에 대해 n번의 연산을 수행했다면, 분할 상환 시간은 T(n) / n
• 분할 상환 분석은 모든 입력에 대해 개별 연산의 평균 시간을 구하는 것으로, 평균 시간 분석(average-case analysis)과는 다르다

분석 기법

분할 상환 분석에는 대표적으로 다음 세 가지 방법이 사용된다:

1. 평균법 (Aggregate Method)
   • n개의 연산 전체를 고려하여 총 시간 복잡도를 계산한 후, 이를 n으로 나눔
   • 가장 단순하고 직관적인 방식

1. 회계법 (Accounting Method)
   • 각 연산에 "가상 비용(credit)"을 할당
   • 어떤 연산은 실제보다 높은 비용을 지불하고 잉여를 남기며, 어떤 연산은 그 잉여를 사용
   • 총 지불 비용이 전체 실행 시간보다 크지 않도록 설계

1. 잠재적 함수법 (Potential Method)
   • 자료구조 상태를 표현하는 잠재 함수 Φ를 정의
   • 각 연산의 분할 상환 시간 = 실제 수행 시간 + Φ(현재 상태) − Φ(이전 상태)
   • 구조의 상태 변화까지 비용에 반영함으로써 정확한 분석 가능

예시

• 동적 배열의 삽입 연산
  • 배열이 꽉 찼을 때 크기를 두 배로 늘리는 과정은 O(n)
  • 대부분의 삽입은 O(1)이지만, 재할당 시는 비쌈
  • n번 삽입 시 총 시간은 O(n) → 분할 상환 시간은 O(1)

• 이진 카운터 증가
  • 1을 더할 때마다 여러 비트를 뒤집을 수 있음
  • n번 증가 연산의 총 비용은 O(n) → 연산당 평균 O(1)

• 스택에서의 push, pop, 그리고 multipop
  • multipop은 한 번에 여러 값을 꺼내지만, 전체 pop 수는 push 수를 초과할 수 없음
  • n번 push, multipop 연산 시 총 비용은 O(n) → 연산당 O(1)

특징

• 최악의 경우 분석보다 현실적이며, 평균 시간 분석과는 다름
• 입력 분포가 아니라 연산 시퀀스에 대해 분석
• 알고리즘이 복잡하더라도 상환 관점에서 간결한 분석 가능

같이 보기

• 분할 상환 시간 복잡도
• 시간 복잡도
• 평균 시간 복잡도
• 동적 배열
• 이진 카운터
• 잠재적 함수법

참고 문헌

• Tarjan, R. E. (1985). Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods, 6(2), 306–318
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press