알고리즘 ) Array Doubling/분할상환분석

안녕하세요. 오늘은 Array Doubling에 대해 알아봅시다XD

자. 우리가 연산이 시작할 때 배열의 크기가 얼마나 필요한지 미리 알수있나요?

(인풋 크기가 정해져 있지 않는다면)

네. 대부분 모르죠.

Array Doubling

---

그러면 만약 연산을 수행하다가 배열이 꽉찼다고 생각해볼게요.

그럼 

배열의 크기를 

어떤 상수 c만큼 늘리는 것 VS 두배 늘리는 것

어느것이 더 효율적이라고 생각하시나요?

내가 지금 필요한 상수 c만큼 늘리는 것이 더 효율적으로 보일수도 있지만, 

사실은 2배 늘리는 것이 훨씬 더 효율적이고 빠르답니다.

그래서 "Array Doubling"이라고 불리죠.

우리는 이제 Array Doubling전략을 한  번 써볼게요.

어떤 방이 있다고 생각해 볼게요. 방의 수용인원은 제한되어 있습니다.

이 방에 사람들을 넣어볼게요.

만약 이 방의 수용인원이 60명이었어요!

그래서 60명의 사람들이 들어가게 됩니다.

61번째 사람은 이 방에 들어갈 수 있나요?

네 ㅠㅠ못들어가죠. 왜냐구요? 이 방의 수용인원이 꽉 차게 되었으니까요.

그럼 우리는 무슨 전략을 쓴댔죠?

네. Array Doubling을 해보겠습니다.

이방의 수용인원(배열의 크기)가 60이었으니 이 크기의 두배인 120명을 수용할 수 있는 방으로 갈거에요.

지금 이 방을 공사해서 늘릴수는 없겠죠? 아예 새로운 방으로 갈거에요. 

120명을 수용할 수 있는 방으로요!!

자, 그럼 원래 방(A라고 하겠습니다)에 들어있던 60명의 사람은

120명을 수용할 수 있는 방(B라고 하겠습니다.)으로 가야겠죠?

그래서 일단 한 사람을 옮기는 비용을 t라고 가정해봅시다. 

(이것을 transferring cost)라고 해요.)

그럼 한사람을 옮기는데 t면 60명을 옮기는 데는 얼마죠? 네. 60*t겠네요.

만약 n명이었다면? 네. t*n입니다. 

일단 지금 우리가 알 수 있는 것은 이 방에 n명의 사람들이 있기때문에 

(예제에서는 60이죠?)

이 사람들을 옮기는 비용은 무조건 지불해야한다는 거죠.즉, t*n의 비용을요.

자, 그럼 t*n만 지불하면 끝일까요?

아닙니다.

이 t*n의 값은 "현재" 지불해야할 transferring cost이죠? 

그렇다면,이렇게 한번생각해봅시다.

현재 이 방의 수용인원이 60명이랬죠? 알고보니까, 이 방도 이 전에 더블링이 일어난 상태였던거죠.

그럼 이 전 방의 수용인원은 30명 이었겠죠? (60/2)

그럼 30명이었을 때는 transferring cost가 얼마였을까요?

네 현재 인원(60)의 반(30)에 t를 곱한 30t겠죠? 

30명도 더블링 된 상태였다면? 15t의  transferring cost가 발생했을 겁니다.

이것을 일반화 시키면 현재 크기 n까지 오기 직전에 transferring cost의 총합은 t*n/2 +  t*n/4 + t*n/8..... 을 더한 t*n보다는 작거나 같을거에요

최종적으로,현재 더블링이 일어나서 이 방의 인원을 옮겨야 할 때 지불해야할 비용 t*n과,

현재 더블링이 일어나기 전까지 더블링이 일어났을 경우 그 때의transferring cost의 합인 t*n을 더한

t*n+t*n = 2*t*n의 transferring cost가 필요하게됩니다.

조금 이해가 가시나요?

이 Array Doubling은 Amortized Analysis에서도 설명하기 위해 쓸 예정이라..

알아두시면 좋아요.

ㅎㅎ

도움이 되었으면 좋겠어요!!