알고리즘 ch 6 array doubling

Dynamic Sets and Searching

Array Doubling

- 배열의 크기를 늘려야 할 때 원래 배열의 2배 크기를 할당 받아 원래의 배열에 있던 값들을 옮기는 작업. 

- 값을 하나 옮길 때 t시간이 덜린다고 하면, size n의 배열에 n+1번째 값이 들어올 때 2n개의 새로운 메모리를 할당 받아 n개의 값들을 옮기고 n+1번째의 원소를 입력해야 한다. 

  이 작업에는 기존 n개의 원소를 옮길 때 t*n의 시간이 필요할 것이다.

  그럼 이 작업을 포함해 이전의 총 이동 시간을 생각해보면

  t*n + t*n/2 + t*n/4 + ... = t(n + n/2 + n/4 + 1) 의 시간이 걸렸을 것이며

  이는 총 2t*n보다는 적게 걸렸을 것이다.

Array doubling이 중요한 이유는 1개의 원소를 입력할 때 그 원소가 몇 번째로 입력된 것인가에 따라 t의 시간이 걸릴 수도 있고 ktn+1의 시간이 걸릴 수도 있기 때문이다. 

이런 (발생할 수 있는 최악의 경우)측면을 고려한 분석방법이 amortized analysis이다.

Amortized Analysis 분할 상환 분석

- 최악의 경우를 고려한 평균을 분석 하는 방법

- 기존에 배웠던 Asymptotic analysis의 경우 Big-O 표기법일 시 

  최악의 경우가 거의 발생하지 않아도 최악의 시간 복잡도를 알고리즘의 복잡도로 생각한다.

  ex) 대부분 O(1)이고 간혹 O(n)이라도 O(n)으로 취급

  이러한 경우를 방지하기위해 Amortized Analysis를 사용하는것

- Amortized Analysis 종류

 1) Accounting method

 2) Aggregate method

 3) Potential method

 -> 이 중, account method에 대해서 다뤄보겠다.

- Account method : doubling상태를 대비해, transfer 비용을 모든 단계에 배분해놓는다.

    이렇게 함으로써 간혹 발생하는 불균형을 모든 단계로 분산해 평준화시키는 것이다.

  Amortized cost = Actual cost + Account cost

  * Actual cost : 매 알고리즘 당 실제로 들어가는 비용

  * Accounting cost : 특정 시점(최악의 경우)의 연산량을 대비해 미리 쌓아 두는 비용

Stack에 값을 입력push하는 연산 예를 들어보자. 

값을 옮기는 비용은 t, Stack의 초기 메모리는 n , pop과 push는 1의 시간이 걸린다고 가정한다.

Stack에 n+1번째 원소 push에 대한 amortized cost를 구해보자.

doubling이 발생하지 않았을때 push 비용은 1

doubling이 발생했을 때 push 비용은 1 + t*n이다.

doubling이 발생했을 때 doubling transfer 비용은 총 2t*n을 넘지 않는다. 그러므로 모든 단계에 배분해야하는 

accounting cost의 값을 2tn/n = 2t로 둔다.

(1)   Doubling 없을 때 actual cost: 1, accounting cost: 2t => Amortized cost = 1+2t

(2)   Doubling이 있을 때 actual cost: t*n + 1, accounting cost: -t*n + 2t => Amortized cost = 1+2t

따라서 간혹 발생하는 비용을 평준화 한 결과 항상 1 + 2t의 비용이 발생

amortized O(1+2t) = O(1)이 된다.

asymptotic analysis 였으면 최악의 경우를 보고 O(2tn) = O(n)이라고 판단했을 것이다.