Amortized Analysis : 분할 상환

알고리즘의 성능을 분석하는 방법 중 하나이다. 최악의 경우에도 평균적인 실행 시간을 측정하는데 사용한다.

단일 연산에 초점을 맞추는 대신, 여러 연산을 수행 한 후 전체 평균 비용을 계산한다.

간단한 예시 : 증가 가능한 배열, Resizing Array

정적 배열에서 크기가 부족 할 때 동적으로 배열 크기르 늘리는 상황을 생각해보자.

• 배열이 full이면 배열의 크기를 두 배씩 늘린다고 가정한다.
• 각 크기 증가 시, 기존 배열의 모든 요소를 새 배열로 deepcpy 해야한다.

계산 과정

1. 배열에 요소를 추가 할 때
   • 대부분의 경우 요소 추가 비용은 N(1) 상수 시간에 가능하다.
   • 하지만, 배열 크기를 늘릴 때는 복사 비용이 발생하므로, O(n) 비용이 든다. (n : 배열의 기존 크기)
2. 이 연산을 Amortized Analysis로 분석해보자 :
   • 크기 조정은 배열 크기가 두 배가 될 때마다 발생한다.
   • 추가 연산은 n번의 복사가 필요하지만, 이 작업은 전체적으로 보았을 때 n개의 연산에 퍼진다.
     • 여기 중요하다.
     • 특정 고비용의 연산이 발생하더라도, 전체적인 관점에서 그 비용이 각 연산에 "균등하게 분배"된다는 뜻이다. 한 번의 최악 연산이 발생하더라도, 이를 모든 연산에 걸쳐서 나눠서 보면 평균 비용은 낮아진다는 점을 설명하는 것이다.
   • 따라서 평균 비용은 O(1)이 된다.

상세 내용

1. Amortized Analysis에는 세 가지 방법을 논 할 수 있다.
   1. Aggregate Method, 총합법 : 전체 연산의 총 비용을 계산한 다음, 연산 수로 나누어 평균 비용을 구한다.
   2. Accounting Method, 회계법 : 연산에 "가상 비용"을 부여하여 과도한 비용을 분산한다. 잉여 비용은 "저축"으로 남기고, 필요 할 때 사용한다.
   3. Potential Method, 잠재적 에너지 : 데이터 구조의 상태에서 "잠재적 에너지"를 정의하고, 연산 당 변화량을 계산한다.
2. 적용 사례는 이런게 있다.
   1. Stack의 Push/Pop + multi pop : 스택에서 여러 요소를 한 번에 pop하는 연산이 발생 할 경우, 평균적으로 O(1)로 분석 할 수 있다.
   2. Dynamic Table : 크기가 가변적인 해시 테이블에서 재해시(rehashing)가 발생하는 경우, Amortized 비용은 O(1)이다.
   3. Binary Counter : 이진 카운터에서 비트 뒤집기 연산의 Amortized 비용은 O(1)이다.