Amortized Analysis (분할상환분석)

이 분석은 “최악”의 경우에 대한 것이다.

 

Amortized Analysis 정의

“최악의 경우에 대해 최악의 경우가 발생하도록 연속된 연산을 수행하고, 그때 한 번의 연산에 대한 평균수행시간을 분석하는 것”

 

이것이 왜 필요한가?

예를 들어, 비용을 1만큼 쓰는 연산이 있는데 이 연산은 가끔 n번 발생한다고 하면,

Asymptotic analysis(점근적 분석)을 사용하면 이 연산은 O(n)이 된다.

하지만 가끔 일어나는 경우 때문에 O(n)이라고 하기에는 아깝다.

이를 보완하기 위해 나온 분석이 “Amortized Analysis”이다

 

다시 말하면 Amortized Analysis는 최악의 경우에 연속으로 발생하는 연산의 “평균비용”을 의미한다.

 

 

(Array Doubling)

n크기의 배열이 꽉 차 있는 상황에서 원소 하나가 추가될 경우, 크기 n을 상수만큼 늘리는 것이 아니라 2배의 크기의 배열에 옮기는 것을 의미한다. (상수를 더하는 것보다 2배 크기로 설정하는 것이 더 효율적)

 

 

Amortized cost = actual cost + accounting cost

(평균 비용)           (실제 비용)   (계좌에 남아있는 비용)

 

actual cost과 accounting cost는 Array Doubling 유무에 따라 값이 달라진다.

 

예를 들어, n크기의 배열이 있고, 원소 한 개에 대한 비용은 t이다.

현재 배열에는 n개의 원소가 들어있고 1개 원소를 추가할 것이다.

actual cost

Array Doubling X = 1

Array Doubling O = tn+1 (1개 원소 추가할 때)

 

여기서, 이 배열은 전에 Array Doubling이 일어난 걸 수도 있다.

전에 Array Doubling의 transferring cost 총 합 : tn/2+tn/4+tn/8+…<=tn

total transferring cost <= 2tn

 

n번의 연산이 일어났기 때문에 2tn/n = 2t

2t의 비용이 계좌에 있어야 Array Doubling의 발생 유무에 상관없이 모든 비용을 지불할 수 있다.

 

accounting cost

Array Doubling X = 2t

Array Doubling O = 2t-tn (새로운 배열에 transferring cost “tn" 추가)

 

 

Amortized cost = actual cost + accounting cost 공식을 이용하면

Array Doubling X = 1+2t

Array Doubling O = tn+1+2t-tn = 1+2t

 

한번의 push연산에 대한 amortized cost 1+2t 이 된다.

accounting cost은 절대 음수가 되면 안된다.