분할 상환 시간 복잡도 편집하기

분할 상환 시간 복잡도(amortized time complexity)는 일련의 연산 전체에 대한 총 수행 시간을 평균 내어, 각 연산의 평균적 성능을 분석하는 기법이다. 이는 '''개별 연산은 비쌀 수 있지만, 전체적으로는 효율적인 알고리즘'''을 설계하고 분석하는 데 사용된다.
==개념==
어떤 알고리즘이 대부분의 경우 빠르게 동작하지만, 특정 연산에서만 느릴 수 있는 경우, 그 연산 하나만 보고 최악의 시간복잡도를 판단하면 과하게 보수적일 수 있다. 이때 전체 연산 시퀀스를 분석하여, 연산 1회당 평균적인 시간복잡도를 구하는 것이 분할 상환 분석이다.
*총 수행 시간 T(n)에 대해 n개의 연산이 이루어진다면, 평균 시간복잡도는 T(n) / n
==방법==
분할 상환 분석에는 다음 세 가지 주요 기법이 있다:
#'''평균법(Aggregate Method)'''
#*n개의 연산 전체에 대해 총 시간복잡도를 계산한 후, 이를 n으로 나눔
#*가장 직관적인 방식
#'''회계법(Accounting Method)'''
#*각 연산에 "가상 비용(credit)"을 부여해, 싼 연산에서 남긴 비용으로 비싼 연산을 상쇄
#*총 지불한 비용이 실제 전체 시간복잡도를 초과하지 않도록 구성
#'''잠재적 함수법(Potential Method)'''
#*자료구조 상태에 따라 정의된 잠재 함수 Φ를 사용하여 시간 분석
#*실제 시간 + 잠재 에너지 변화량 = 상환 시간
==예시==
*'''동적 배열(dynamically resizing array)의 삽입'''
**배열이 가득 찼을 때 크기를 2배로 늘리며 복사 → O(n) 시간 발생
**하지만 그 외 대부분 삽입은 O(1)
**n개의 삽입 전체에 걸쳐 보면 총 시간은 O(n) → 평균 삽입 시간 O(1)

*'''이진 카운터'''
**카운터의 비트를 1씩 증가시킬 때, 어떤 연산은 여러 비트를 뒤집음
**n번 증가 연산의 총 시간은 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
[[분류:수학]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*