분할 상환 시간 복잡도

분할 상환 시간 복잡도(amortized time complexity)는 일련의 연산 전체에 대한 총 수행 시간을 평균 내어, 각 연산의 평균적 성능을 분석하는 기법이다. 이는 개별 연산은 비쌀 수 있지만, 전체적으로는 효율적인 알고리즘을 설계하고 분석하는 데 사용된다.

1 개념

어떤 알고리즘이 대부분의 경우 빠르게 동작하지만, 특정 연산에서만 느릴 수 있는 경우, 그 연산 하나만 보고 최악의 시간복잡도를 판단하면 과하게 보수적일 수 있다. 이때 전체 연산 시퀀스를 분석하여, 연산 1회당 평균적인 시간복잡도를 구하는 것이 분할 상환 분석이다.

• 총 수행 시간 T(n)에 대해 n개의 연산이 이루어진다면, 평균 시간복잡도는 T(n) / n

2 방법

분할 상환 분석에는 다음 세 가지 주요 기법이 있다:

1. 평균법(Aggregate Method)
   • n개의 연산 전체에 대해 총 시간복잡도를 계산한 후, 이를 n으로 나눔
   • 가장 직관적인 방식
2. 회계법(Accounting Method)
   • 각 연산에 "가상 비용(credit)"을 부여해, 싼 연산에서 남긴 비용으로 비싼 연산을 상쇄
   • 총 지불한 비용이 실제 전체 시간복잡도를 초과하지 않도록 구성
3. 잠재적 함수법(Potential Method)
   • 자료구조 상태에 따라 정의된 잠재 함수 Φ를 사용하여 시간 분석
   • 실제 시간 + 잠재 에너지 변화량 = 상환 시간

3 예시

• 동적 배열(dynamically resizing array)의 삽입
  • 배열이 가득 찼을 때 크기를 2배로 늘리며 복사 → O(n) 시간 발생
  • 하지만 그 외 대부분 삽입은 O(1)
  • n개의 삽입 전체에 걸쳐 보면 총 시간은 O(n) → 평균 삽입 시간 O(1)

• 이진 카운터
  • 카운터의 비트를 1씩 증가시킬 때, 어떤 연산은 여러 비트를 뒤집음
  • n번 증가 연산의 총 시간은 O(n) → 평균 O(1)

4 특징

• 최악의 경우보다 정확한 예측 가능
• 반복되는 연산이 포함된 알고리즘 분석에 적합
• 분석은 비결정적인 입력에도 강건함

5 같이 보기

• 시간 복잡도
• 평균 시간 복잡도
• 최악 시간 복잡도
• 동적 배열
• 이진 카운터

6 참고 문헌

• 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