분할 상환 분석 편집하기

분할 상환 분석(amortized analysis)은 알고리즘의 연산이 반복될 때, 각 연산의 '''평균적 비용'''을 계산하여 알고리즘의 성능을 평가하는 방법이다. 이는 최악의 경우 시간 복잡도보다 더 현실적인 성능 평가를 제공하며, 연산 간 비용이 불균등한 자료구조에서 특히 유용하다.
==개념==
어떤 자료구조에서 일부 연산은 가끔 매우 높은 비용을 요구할 수 있지만, 전체 연산의 흐름에서 보면 대부분 저렴한 연산들이기 때문에, '''총 수행 시간에 기반한 평균적 비용'''으로 각 연산의 효율을 판단한다.
*총 수행 시간 T(n)에 대해 n번의 연산을 수행했다면, '''분할 상환 시간'''은 T(n) / n
*분할 상환 분석은 '''모든 입력에 대해 개별 연산의 평균 시간'''을 구하는 것으로, 평균 시간 분석(average-case analysis)과는 다르다
==분석 기법==
분할 상환 분석에는 대표적으로 다음 세 가지 방법이 사용된다:
#'''평균법 (Aggregate Method)'''
#*n개의 연산 전체를 고려하여 총 시간 복잡도를 계산한 후, 이를 n으로 나눔
#*가장 단순하고 직관적인 방식

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

#'''잠재적 함수법 (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
[[분류:수학]]
[[분류:알고리즘]]