# 분할 상환 분석(Amortized Analysis)
## 참조 사이트
[Eth Dev Post](https://hcn1519.github.io/articles/2017-05/amortized_analysis)

<br>

## 개념
> 주어진 알고리즘의 시간 복잡도나, 프로그램을 수행하는데 소요되는 시간 또는 메모리 같은 자원 사용량을 분석하기 위해서 사용하는 기법입니다.

알고리즘 분석 시 각의 연산마다 최악의 경우를 따지는 것은 굉장히 힘드므로 이를 쉽게 해결하기 위해 `분할 상환 분석`이라는 방법론이 나오게 되었습니다.

<br>

## 평균 수행 시간의 필요성
> 어떤 지표로 분석하는 것이 제일 효율적일까요?

자, 저희는 백화점에서 3벌의 옷을 사야 합니다. 옷은 각각 1만원, 2만원, 3만원이며 구매 시 필요한 총 금액은 6만 원이 됩니다. 그러나 저희가 아는 정보라곤 "**옷 한 벌당 최대 3만원"** 밖에 없습니다. 그렇다면 준비해야 하는 금액은 얼마일까요?

최악의 상황은 3만원짜리 옷을 3벌 사는 것입니다. 총 9만 원이 필요하죠. `옷 한 벌당 최대 3만원`의 정보만으로는 3만원을 더 준비해야 합니다.

만약 `옷 한 벌당 구매 당 평균 비용이 2만 원`이라는 정보를 추가적으로 알게 된다면 우리가 준비해야 하는 금액은 어떻게 될까요? **정확히 6만원만 준비하면 됩니다!** 자세히 살펴볼까요?
1. 평균 비용을 통해 각 옷마다 2만원이 들 것이라 예상하고 6만 원을 준비합니다.
2. 구매하는 옷이 2만원이라면 그대로 2만원을 사용합니다.
3. 옷이 2만원보다 비싸다면 부족한 금액을 2만원보다 싼 옷에서 보충합니다.

너무 당연한 얘기지만 이것이 분할 상환 분석의 핵심입니다. `부족한 금액(최악)` 이나 `남는 금액(최선)` 을 서로 보충하면서 `준비할 금액(평균)` 을 도출하듯 전체 연산의 평균 비용을 계산하는 것이죠!

<br>

## 정리
> 분할 상환 분석은 알고리즘의 수행 시간을 분석하는 방식 중 하나입니다.

기존 알고리즘 수행 시간 분석은 빅오(Big-O) 표기법을 통해 표현했으나, 빅오 표기법은 전체 알고리즘 비용을 최악(Worst)으로 잡기 때문에 실제 연산과 다른 상황이 종종 나타납니다.

결국 분할 상환 분석은 `전체 비용의 평균`이라는 추가 정보를 제공하여 실제 연산의 비용 판단을 도와주는 것입니다.

<br>

<sup>[(상위 문서로)](https://github.com/InSeong-So/IT-Note/blob/master/chapter07-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/DoublingofArray.md#%EB%8D%94%EB%B8%94%EB%A7%81doubling-of-array)</sup><br>
<sup>[(최상위 문서로)](https://github.com/InSeong-So/IT-Note)</sup>

<hr>
<br>