[알고리즘] CH6. Amortized Analysis - Array Doubling

Array doubling

• 사이즈가 n인 배열 A가 있다고 하자.
• A가 꽉 찼을 때, push가 들어온다면
  • 사이즈가 두 배인(2n) 배열 B를 만들어, 배열 A에 있는 것들을 옮기고, 새로운 데이터를 push한다.
  • 이때, (n*t+1)만큼의 연산을 한다.
  • t: A에서 B로 데이터를 하나 옮기는데 드는 시간
  • 1: 새로 들어온 데이터는 처음부터 B로 들어감
• 그렇다면, push 연산의 시간 복잡도는 O(n)이다. 
  • 하지만, doubling은 가끔씩만 발생하는데 O(n)으로 취급하기는 아깝다 ㅠㅠ
  • -> Amortized Analysis를 하자! 

 

 

Amortized Analysis

• worst case 분석
• 연속해서 연산이 발생할 때, 최악의 경우의 평균 연산을 고려한다.
• Average Analysis와의 차이
  • Average analysis: 확률을 이용하여 계산
  • Amortized analysis: 확률 이용 x, 최악의 경우의 평균을 이용
• Accounting method
  • 미래에 지불할 돈(최악의 경우)을 대비해 매일 저축하는 것.
  • Amortized cost = actual cost + accounting cost
  • actual cost: 각 연산에 실제 드는 cost
  • accounting cost: 미래에 들 cost를 대비해 매일 저축하는 cost
    • accounting cost의 합은 non-positive
    • 즉, (현재 저축해둔 돈 - 현재 지불할 금액)이 음수이면 안됨

 

 

Array에 값 넣기(push)

• 배열에 자리가 남은 경우 push 연산 -> actual cost: 1
• 꽉 찬 배열에 push 연산 -> actual cost: n*t+1

 

 

전체 push 연산 cost를 계산해보자

• 현재 배열 사이즈가 n일 때, 2n 사이즈의 배열로 doubling이 발생했다면 -> cost: n*t  (1 생략)
• 그렇다면 그 전에는, 배열 사이즈가 n/2인 배열이 n으로 doubling 했었을 것이다.

 

• Accounting cost는 total cost의 평균으로 설정한다.
• accounting cost = 2tn/n =2t
• 즉, 매 연산마다 2t씩 저축한다.

 

Push 연산

• doubling이 발생하지 않을 때,
  • actual cost: 1
  • accounting cost: 2t       -> 원래 사용한 만큼 빼줘야 하는데 (2t-1), 1은 그냥 무시하는 듯
  • amortized cost: 1 + 2t
• doubling이 발생한 경우,
  • actual cost: nt +1
  • accounting cost: 2t - nt   -> 사용한 만큼 빼줌(1은 무시하는 듯) 
  • amortized cost: 2t + 1
• 즉, push 연산에 대한 시간 복잡도는 O(2t+1)
  • t가 상수 시간이라면 -> amortized O(1) time이 된다.