알고리즘 ) Amortized Analysis

안녕하세요. Zedd입니다ㅎㅎ

아까전에 어떤분이 <Array Doubling/분할상환분석>글을 잘 봤다고 메세지를 주셨어요 :)

원래 <Array Doubling/분할상환분석>글도 Amortized Analysis를 쓰기 위해서 썼던건데...

이참에 얼른 써야겠다고 생각했어요 XD

그래서 오늘은 Amortized Analysis에 대해 알아보겠습니다!!

Amortized Analysis

---

Amortized Analysis...? 뭔 분석같은데..라고 생각하실거에요 :)

한글로 하면 분할상환분석이라고 한답니다. 

저는 "에모타이즈드 어날리시스"라고 부르는게 편해서 그렇게 부르고 있어요.

그래서 이 Amortized Analysis가 무엇이냐!

저도 알고리즘시간에 처음 배웠답니다. 

간단하게 Amortized Analysis의 정의를 말씀드리자면,

"최악의 경우에 대해 최악의 경우가 발생하도록 연속된 연산을 수행하고, 

그때의 한번의 연산에 대한 평균수행시간을 분석하는것"

..?

일단 잘 모르겠네요..정의만 봐서는

음.. 설명드리기전에 

혹시  Asymptotic analysis는 아시나요?

점근적 분석이라고 부르는거말이죠!

네. 이거는 익숙하실거에요. 

인풋개수 n에대해 알고리즘의 수행시간을 분석하는 방법이죠.

Amortized Analysis도 마찬가지입니다. 

수행시간을 분석하는 방법이에요.

Asymptotic analysis와 뭐가 다르냐!!!

자. 어떤 연산이 일어난다고 생각해봅시다.

그 연산에 대해 "평소"에는 연산에 대한 비용이 1이라고 생각해봅시다. 

이것만 생각하면 O(1)이라고 볼 수 있습니다.

 하지만, 정말정말정말 가끔 n번의 연산이 일어납니다.

그럼 Asymptotic analysis를 하면 위의 연산은 O(?)이 될까요? 

최악의 경우 n번의 연산이 일어나므로 O(n)이죠? 

하지만, 진짜 가끔씩 n번의 연산이 일어나는데 (대부분의 연산이 1인데) O(n)으로 분석하기 너무 아깝다는거죠.

O(1)으로 해도 되는데!!!! 정말 아깝게 그 가끔의 n번의 연산때문에!!!

Asymptotic analysis에 의해O(n)이 된거죠.

이러한 경우때문에 Amortized Analysis가 나오게 되었습니다.

간단하게 말하면, 위와같은 예제는

 Asymptotic analysis로 알고리즘을 분석했을 때는 O(n)이지만, Amortized Analysis로 하면 O(1)인거죠.

대신 그냥 O(1)이라고 하면 안되고, Amortized O(1)이라고 해야합니다.

(그리고 헷갈릴 수도 있는데, Amortized Analysis는 최악수행시간분석입니다.)

자, Amortized Analysis를 하는 이유는 이제 아시겠죠?

그럼 도대체 어떻게 하냐!!!!!

그것을 알아보겠습니다. 

그 전에, 알아두셔야 할 것이 있는데 바로

"Array Doubling" 입니다. 다들 읽고오셨죠? ㅎㅎ

< Array Doubling 읽으러가기 >

읽고오셨다고 생각하고 글쓸거에요 :)

자, 진짜 Amortized Analysis를 알아보러 가봅시다. 

Amortized Analysis에도 수행시간을 분석하는 여러가지 방법이 있는데요,

그중에서 저는 accounting method를 설명드릴거에요.

(제가 이것만 배웠기 때문....)

accounting method란 연속적인 연산들이 최악의 경우를 만들 때,

그때의 한번의 연산에 대한 "평균비용"을 구하는 방법입니다.

※ 비용!!!!잊으면 안돼요. 우리는 이제 "비용"을 구할거에요. cost!!!!!!비용!!!

비용? 갑자기 웬 비용을 구하는거죠? 수행시간 분석하다말고..?

자. 어떤 연산이 공짜로 이루어지지 않죠?

어떤 연산을 수행하려면 지불해야하는 "비용"이 있습니다.

이번 예제에서는 Stack의 push로 예를 들거에요.

accounting method는 이렇게 정의돼요.

amortized cost = actual cost + accounting cost

여기서 amortized cost는 바로 우리가 구할 "평균비용"입니다. 

평균적으로 어떤 연산에 지불해야 할 비용이 얼마냐?

를 구할거에요. 

이 amortized cost는 0보다는 커야합니다. 

그리고 actual cost.

실제비용? 

네. 맞아요. 우리가 아까 Stack의 push를 예로 들거라고 했죠?

이 push. push가 공짜로 이루어지진 않아요. 이 push를 하는데 드는 비용을 actual cost라고 합니다.

마지막으로 accounting cost. 

account는 계좌라는 뜻을 가지고 있죠? 

간단하게 accounting cost는 우리가 가지고 있는 "남아있는 비용"이에요.

아직 이해가 잘 안가시죠?

당연합니다.

걱정하지마세요!

자, 정리하면

accounting method는 어떤 연산에 대해 비용을 지불하는데, 그 비용은 실제 일하는데 쓰는 비용 + 적립하는 비용 = amortized cost.라고 합니다. 이게 얼마인지 알아내는 것이 accounting method의 목적이에요. 

자. 위에서 Stack의 push를 예를 든다고 했죠?

진짜 한번 Stack을 예로 봅시다. 

<Stack>

Stack에서의 연산 중 push와 pop이 있죠? 우리는 이 push와 pop이라는 연산의 실제비용(actual cost)를 1로 줄거에요.

그러니까, Stack에 어떤 값을 넣거나 빼는데에 비용이 1이 드는거죠.

이때의 1이라는 비용은 Doubling이 일어나지 않았을때의 actual cost입니다. 주의하세요.

근데 만약에 Stack(Stack A)이 꽉찼어!!

그럼 우리 현재 크기의 두배 크기인 Stack을(Stack B) 하나 잡고, 여기로 다 옮긴다고 그랬죠?

드디어 Doubling이 일어난거죠.

그럼 지금 현재 Stack A에 들어있는 값들을 Stack B에 넣어줘야하겠죠? 

여기서 우리가 저번시간에 배웠던 tranferring cost가 나오게 되는데요,

저번시간에, 한 사람?을 옮기는데 드는(한 element를 copy하는데 드는)  tranferring cost를 t라고 했을 때, n명의 사람들 옮기는 데 t*n이 든다고 그랬고,

이 전  tranferring cost까지 다 고려했을 때,  tranferring cost의 총 합은 2tn보다는 작을거라고 말씀드렸어요.

그럼 Stack A에 있는 것을 Stack B로 옮겨봅시다.(지금은 Doubling이 일어난 상태에요!)

한 원소를 옮기는데 드는 비용을  t라고 했으니, Stack A에 n개의 원소가 있었다면, t*n의 비용이 들겠네요.

그리고!!!!!

지금 이 Doubling을 트리거시킨 원소가 있겠죠? 

딱 push하려고 했는데 Stack A가 꽉차서 못넣었던 그 원소요.

그것도 이제 Stack B에 넣어줘야겠죠?

그럼 1이라는 비용이 들것입니다.(Doubling은 안일어났으니까요.)

그렇다면 최종적으로, Doubling이 일어났을 때의 actual cost는 1+t*n이라고 할 수 있습니다.

(Doubling을 트리거시킨 원소 + Stack A에 있는 원소들을 Stack B로 옮기는 비용)

자 Stack에서의 actual cost에 대한 개념을 조금 아시겠나요?

이제 Accounting cost로 가볼까요? 

Accounting cost를 이야기하기전에, 알아야하는 사실 한가지가 있습니다. 

accounting cost가 제가 지금 가지고 있는 비용이라고 그랬죠?

제가 가지고 있는 비용이 0이면 push고 뭐고 아무것도 못하는거에요.

우리는 위해서 transferring cost의 총 비용이 2tn이라는 것을 알아요.

우리가 총 n번의 push가 일어났다고 했을 때(정확히는 n+1), 2tn/n을 한 값. 즉 2t를 제 계좌에 넣어야만 모든 push연산에 대해 버틸 수 있습니다. 

push할 때 쓰는 비용은 Doubling이 안일어났을때는 1,  Doubling이 일어났을 때는 1+tn이라고 그랬죠?

이 모든 상황에 대해서 언제든 위 비용을 지불 할 수 있으려면, Doubling이 일어났든, 일어나지 않았든 저는 2t를 제 계좌에 꼬박꼬박 넣어야합니다.

그래야만 Doubling이 일어났을 때, 일어나지 않았을 때 이 모든 비용을 낼 수 있어요.

그러니까!!!!!!!제가 하고싶은 말은

Doubling이 일어났든 안났든 2t라는 것이 제 accounting cost라는 것이죠.

제 계좌에는 2t가 꼬박꼬박 쌓이고있어요.

근데!!!!Doubling이 일어났다고 생각해봅시다. 우리

Doubling일어나면  1+tn이라는 비용이 "필요하죠?"

이 비용은 제 계좌에서 가져오는거에요.

그러니까!!!!!!!!!!!!!!!

Doubling이 일어나는 순간 제 계좌에는 2t가 적립될 뿐만아니라, 1+tn이 빠져나가게 되죠. (여기서 1은 무시하는 것 같아요.)

정리하면, Doubling이 일어났을때의 push연산에 대한 accounting cost는 -t*n+2t입니다.

자. 우리지금 actual cost와 accounting cost를 다 배웠어요.

amortized cost가 뭐랬죠?

actual cost+accounting cost라고 그랬죠? 

Doubling이 안일어났을 경우 : 1+2t

Doubling이 일어났을 경우 : (1+tn)+(2t-t*n) = 1+2t

즉!!!!!!!!!!!!!!!!!!!!

Array Doubling을 이용해 구현한 Stack의 push연산에 대한 복잡도는 amortized O(1+2t).

즉. O(1)이게 됩니다!!!!!!!!!!!!!!!!!!!!!!!!

원래 점근분석으로 하면 O(n)인데 말이죠!!!!!!!!!!

(n개의 원소가 2n사이즈로 옮긴다고 했을 때, 그 다음 insert가 t*n+1이므로.)

흠.................ㅎㅎ...이해가 잘 가셨을지 모르겠어요.

저도 수업시간에 배울 땐 정말 어려웠답니다 ㅠㅠ

이해가 안가시는 부분은 댓글이나, PC화면 오른쪽 하단에서 볼 수 있는 채널서비스를 이용해주세요 :)

감사합니다!!! 이 글이 Amortized analysis를 이해하는데 도움이 되었으면 좋겠네요 XD..