Amortized Analysis - Amortized cost란 무엇인가?

* 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다.

 

오늘은 Amortized Cost를 구하는 Amortized Analysis를 알아보도록 하겠다.

가상의 예를 들어보겠다.

 

우리가 스타트업 가게를 차렸다고 가정하자. 

새로운 고객이 서비스를 사용할때마다 counter가 올라가고(binary counter) 그에 따라 $1불씩 전기회사에 비용을 지불한다. 

이때 이 지출비용을 커버하기 위해 각 고객별로 얼마를 받아야할까?

 

첫 8명의 고객을 받았을때 지출이 얼마나 되는지 살펴보자

이때 cost는 flip하게 되는 bit의 개수를 의미한다. 

counter	User #	Cost
0 0 0 0 0 0	1	1
0 0 0 0 0 1
0 0 0 0 0 1	2	2
0 0 0 0 1 0
0 0 0 0 1 0	3	1
0 0 0 0 1 1
0 0 0 0 1 1	4	3
0 0 0 1 0 0
0 0 0 1 0 0	5	1
0 0 0 1 0 1
0 0 0 1 0 1	6	2
0 0 0 1 1 0
0 0 0 1 1 0	7	1
0 0 0 1 1 1
0 0 0 1 1 1	8	4
0 0 1 0 0 0

cost가 vary하는 현상을 볼 수 있다. 

 

해결책1) 각 사용자에게 실제 cost를 부여한다.

-> 각 사용자별로 다른 cost를 charge할 수는 없다. 

 

해결책2) 각 사용자에게 가능한 maximum cost를 부여한다.

그렇다면 그 maximum cost는 얼마일까?

위 예시에서는 총 6 bits이기 때문에 최대 $6를 charge할 수 있다. 

일반화하면 n bit에서는 $n을 charge할 수 있다. 

-> 너무 비싼 가격으로 사용자가 오지 않을 수 있다

 

그렇다면 누적된 total cost를 계산해보자.

total cost = 현재 sign up 한 user까지의 모든 cost의 합

counter	User #	Cost	Total Cost
0 0 0 0 0 0	1	1	1
0 0 0 0 0 1
0 0 0 0 0 1	2	2	3
0 0 0 0 1 0
0 0 0 0 1 0	3	1	4
0 0 0 0 1 1
0 0 0 0 1 1	4	3	7
0 0 0 1 0 0
0 0 0 1 0 0	5	1	8
0 0 0 1 0 1
0 0 0 1 0 1	6	2	10
0 0 0 1 1 0
0 0 0 1 1 0	7	1	11
0 0 0 1 1 1
0 0 0 1 1 1	8	4	15
0 0 1 0 0 0

위 표에서 보면 total cost가 2*user #보다 늘 작다는 것을 볼 수 있다. 

 

이를 통해 

해결책3) 각 사용자에게 $2을 charge한다.

-만약 실제 cost가 $2보다 적다면 남은 차이는 savings에 넣을 수 있다.

- 만약 실제 cost가 $2보다 크다면 savings에 넣어뒀던 cost를 사용한다.

 

이 해결책이 제대로 작용하는지 실제로 확인해보자. 

counter	User #	Cost	Total Cost	Total Income	Savings
0 0 0 0 0 0	1	1	1	2	1
0 0 0 0 0 1
0 0 0 0 0 1	2	2	3	4	1
0 0 0 0 1 0
0 0 0 0 1 0	3	1	4	6	2
0 0 0 0 1 1
0 0 0 0 1 1	4	3	7	8	1
0 0 0 1 0 0
0 0 0 1 0 0	5	1	8	10	2
0 0 0 1 0 1
0 0 0 1 0 1	6	2	10	12	2
0 0 0 1 1 0
0 0 0 1 1 0	7	1	11	14	3
0 0 0 1 1 1
0 0 0 1 1 1	8	4	15	16	1
0 0 1 0 0 0

total income =  2* user #

savings = total income - total cost

=> 지출을 커버하기에 충분하다

=> 늘 savings에 돈이 여유가 있다.

 

하지만 user가 훨씬 더 커져도 여전히 충분할까?

 

프로그래밍 관점에서 보자면 여기에서의 counter는 data structure이며 각 사용자가 sign-up하는 것을 operation이라고 볼 수 있다. 

이때 이 operation을 수행하기 위한 cost가 바로 bit을 flip하는 것이다. 

또한 savings >=0 는 data structure invariants이다. 

 

그렇다면 savings는 무엇을 나타낼까?

Savings는 각 bit에서 1의 갯수와 동일하다. 

1의 개수를 token이라고 부른다면  operation을 수행할때마다 2개의 token을 얻고 (사용자에게 $2를 받았던 것)

flip을 할때마다 1개의 token을 잃어버리게 된다. (전기회사에 $1 지불)

 

이를 우리는 token invariant라고 부른다.

# tokens = # 1 bits

 

다른 invariant처럼 이것이 operation을 여러번 거쳐도 유지되는 invariant라는 것을 증명해야한다. 

 

INIT:  사용자가 없을때는 counter = 0 0 0 0 0 0이므로 사용되는 token이 없고 1 bit도 없으므로 # tokens = # 1 bits

 

PRES: 만약 counter를 증가시키기 전 # tokens = # 1 bits 이라면 증가시킨 후에도 # tokens = # 1 bits이다.

이를 수식으로 나타내면 # 1 bits before + 2 - # bit flips = # 1 bits after이 된다. 

 

이를 통해 각 사용자에게 $2을 charge하는 것이 적절한 해결책임을 알 수 있다. 

 

이때의 $2를 우리는 amortized cost라고 부른다. 

실제 cost는 아니지만 여러 opeartion을 거치면서 발생하는 실제 cost를 커버할 수 있는 cost를 말한다. 

 

Amortized Complexity Analysis

위 예시를 통해 우리는 k번의 operation을 행하는 data sturcture가 있음을 확인했다. 따라서 실제 actual cost는 worst case complexity보다 낮을 수 있다. 

actual cost = sum of cost of operation

 

이때 우리는 amortized cost를 전체 실제 cost를 실제 sequence의 길이로 나눈 값이라고 정의할 수 있다. 

amortized cost = actual cost / k

 

이는 실제 actual cost의 평균값과 같은데 이는 sequence의 모든 operation이 같은 비용을 가진다는 것을 보여주기도 한다. 

 

이전 time complexity를 계산할때 우리는 average-case complexity를 확인한 적이 있다.

이것은 chance에 의해서 발생하는 것이라는 걸 알 수 있다. 

차이점을 보자면

 

Average-case complexity: input distribution에 따른 평균(average over chance)

Amortized complexity: operation의 sequence에 따른 평균(average over time)

-각 operation의 cost를 정확히 알 수 있다. 

 

Example 1)

제빵사가 빵 100개당  $100어치의 밀가루를 샀다고 하자.

이때 각 빵별 평균 값으로 $1를 소비하게 된다. 

이때 worst-case 와 amortized cost모두 O(1)이 된다. 

(worst-case: 한개의 빵만 $100를 소비할 경우, amortized: 빵별 평균 $1소비할 경우)

 

Example 2)

평소 우리가 핸드폰을 사용하는 경우는 시간에 따라 다르다. 

하루종일 보게 되는 경우도 있고 거의 보지 않는 경우도 있다. 이때

우리가 통신사 비용을 달별 같은 비용을 낸다.

이때 provider는 우리에게 amortized cost를 charge하는 것이다.

 

Amortized cost를 통해 우리는 실제 cost가 worst-case completiy * k보다 더 적다는 것을 알 수 있다.

Amortized cost를 통해 우리는 미래의 operation에 사용할 비용을 미리 지불하는 것이다. 

 

그렇다면 우리는 어떻게 amortized cost를 찾을 수 있을까?

1) token의 개념을 도입해라. cost하나가 사용될때 token이 하나가 필요하다고 생각하자

2) 각 operation별로 token이 몇개 사용될지를 생각해보자

3) Token invariant를 세운다. 각 operation별로 얼마나 많은 token이 필요한가?

4) 모든 operation이 token invariant를 보장한다고 증명하라

saved tokens + amortized cost - actual cost = saved tokens after

 

이어 다음편에서 이를 활용한 unbounded arrays를 살펴보겠다.