[알고리즘 6강] 상각 분석법

1. 개념

알고리즘의 시간 복잡도를 분석하는 기법

• 연산의 수행 횟수/시간이 독립적으로 결정되지 않고 가변적인 경우

  • 앞서 수행된 연산에 따라 실행 시간이 달라질 때,
    실제 최악 수행 시간을 보다 더 정확하게 분석하는 방법.

상각 분석법의 종류

• 합계 분석

  • 알고리즘에서 해당 연산의 호출 전체에 대한 최악의 수행시간을 분석하고,
    이를 호출 횟수로 나누어 상각시간을 계산

• 회계 방법

  • 먼저 사용하는 연산 종류별로 상각 시간을 할당하고,
    실제 연산을 수행할 때 생성되는 자료구조에 회계 장부를 만들어
    예치와 인출을 통ㅌ해 관리하는 방법

• 위치 에너지 방법

  • 각 연산에 상각 시간을 할당하고 남는 상각 시간을 위치 에너지로 보관하거나
    실제 수행 시간에 모자라는 시간을 위치 에너지에서 빼서 보충하는 방법

---

2. 합계 분석

최악의 실행 시간 $T(n)$

• 각 연산이 포함되는 일련의 연산 전체가 실행될 때 걸리는 최대 시간

• 각 연산의 상각 시간
  • 최악의 실행 시간 / 적용된 연산 개수 -> $T(n) / n$
  • 최악의 경우에 대한 평균값

특징

• 평균값, 하지만 최악의 경우에 대한 값
• 연산의 종류를 구분하지 않고, 모든 연산이 하나의 상각 시간을 가짐

변형된 스택 연산

MultiPop(S, k) {
	while not Stack-Empty(S) and k != 0
    	do Pop(s)
        	k = k-1
}

• 빈 스택에서 Push, Pop, MultiPop으로 구성된 n개의 연속된 연산을 처리하는데 걸리는 시간
  • 스택에 최대의 n개의 객체가 들어갈 수 있으므로
    MultiPop 연산을 1회 실행하는 최악의 시간은 $O(n)$
  • 이와 같은 연산이 n번 반복되는 경우가 최악이고 수행 시간은 $O(n^2)$

• 합계 분석에 의한 상각 분석
  • MultiPop 내부에서 호출되는 Pop을 포함하여
    Pop이 호출될 수 있는 최대 횟수는 최대 Push의 개수와 같으므로
    최대 n이 되고, n번 연산의 최악 수행 시간은 $O(n)$이다.
• 각 연산의 평균 수행 시간
  • $O(n)/n$ = $O(1)$

이진 카운터

$A[k-1]A[k]....A[1]A[0] = x = \displaystyle\sum_{i=0}^{k-1}{A[i]*2^i}$

Increment(A){
	i = 0
    while i < length[A] and A[i] == 1 {
    	do A[i] = 0
        i = i + 1
    }
    if i < length[A] {
    	then A[i] = 1
    }
}

• 수행 시간

  • 바뀐 비트의 개수

• 초기 상태에서 n번 수행할 때, 1회 연산의 상각 시간?

• 기본 적인 분석

  • 최악의 경우는 모든 비트가 1인 경우 -> $\theta(k)$
  • n번 Incremenet 연산의 수행 시간 -> $O(nk)$

• 합계 분석에 의한 상각 분석

  • 1번 수행할 때 변하는 비트의 개수

    • $0 \leq i \leq \lfloor{lgn}\rfloor$ 이면 $A[i]$ -> $\lfloor{n / 2^i}\rfloor$
    • $\lfloor{lgn}\rfloor < i$이면 $A[i]$ -> 0번
      
      

  • n번 수행할 때 변하는 횟수

    • $\displaystyle\sum_{i=0}^{\lfloor{lgn}\rfloor}{\lfloor{\frac{n}{2^i}}\rfloor} < \displaystyle\sum_{i=0}^{\infty}{\lfloor{\frac{1}{2^i}}\rfloor} = 2n$

  • 1회 연산에 대한 상각 시간

    • $O(n)/ n = O(1)$

---

3. 회계 방법

회계 (accounting) 계정 처리와 유사한 개념을 사용

• 각 연산마다 적절한 자본금을 미리 정해 할당

  • 자본금 = 상각 시간

  • 각 연산별로 다른 상각 시간을 가짐

    • 연산의 실제 비용 < 자본금 -> 남는 금액(시간)을 예금
    • 연산의 실제 비용 > 자본금 -> 부족한 금액을 인출

• 최악의 실행시간의 상한
  • 알고리즘에서 적용된 연산들의 자본금 합계

변형된 스택 연산

각 연산바마다 상각 시간 할당

연산명	실제 수행시간	할당한 상각 시간
Push	$1$	$2$
Pop	$1$	$0$
MultiPop	$min(k, s)$	$0$

• Push 연산

  • 1원 -> 실제 Push 연산 수행을 위해 지불
  • 1원 -> Pop 연산을 대비해서 미리 지불한 돈

• Pop, MultipPop 연산 -> 상각 시간 불필요

• 임의의 n개의 연산들에 대한 상각 시간의 합이 실제 연산 시간의 상한

  • 총 상각 시간의 합 $O(n)$
    • 실제 연산 시간의 합 $O(n)$

이진 카운터

• 수행 시간

  • 바뀐 비트의 개수

• 비트의 값을 1로 바꿀 때 상각 시간 2원 할당

  • 0에서 1로 바꿀 때
    • 1원 -> 해당 비트를 세팅하는 데 사용
    • 1원 -> 나중에 해당 비트를 다시 0으로 바꿀 때 사용
  • 1에서 0으로 바꿀 때
    • 해당 비트에 저장된 1원 사용 -> 별도의 상각 시간 불필요

• 1회 연산의 최대 상각 시간 2원

  • n번 연산의 최대 상각 시간 -> $O(n)$

---

4. 위치 에너지 방법

각 종류의 연산마다 상각 시간을 할당 ( 회계 방법과 여기까지는 동일 )

• 각 객체에 대한 남는 상각 시간을 저장하지 않음
  • 전체 자료구조에 대하여 남는 상각 시간을 위치 에너지처럼 생각하고 저장한다.

• i번 째 연산의 상각 시간

  • i번째 연산의 실제 수행 시간 + 위치 에너지의 변화량

  • $\hat{C_i} = C_i + \phi(D_i) - \phi(D_{i-1})$

    • $D_i$ : $D_{i-1}$에 i번째 연산이 수행된 상태의 자료구조
    • $\phi({D_i})$ : 자료구조 $D_i$를 실수값으로 변환하는 함수

• 최악 수행 시간의 상한

  • n개의 연산에 대한 상각 시간의 총합

  • $\displaystyle\sum_{i=1}^n{\hat{c_i}} = \displaystyle\sum_{i=1}^{n}(c_i + \phi({D_i})- \phi(D_{i-1}))\\ = \displaystyle\sum_{i=1}^{n}{c + \phi(D_n)-\phi(D_0)}$

    • $\phi(D_0) = 0$으로 정의, $\phi(D_i) \geq 0$임을 보임

• 상각 분석 과정

  • 위치 에너지 함수 $\phi$ 정의

    • 모든 i에 대해 $\phi(D_i) \geq \phi(D-0) = 0$ 을 만족

  • 연산의 상각 시간을 계산

    • $\hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1})$

  • 적된 연산들에 대한 상각 시간의 합 $\displaystyle\sum_{i=1}^{n}{\hat{c_i}}$ 를 최악의 시간 복잡도로 취함

변형된 스택 연산

$\phi$ -> 스택에 들어있는 객체의 개수

• $\phi(D_0) = 0$,$\quad$ $\phi(D_i) \geq 0 = \phi(D_0)$

• Push 연산 (스택에 s개의 객체가 있는 경우)

  • $\phi(D_i) - \phi(D_{i-1}) = (s+1) - s = 1$
    • $\hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1}) = 1 + 1 = 2$

• MultiPop 연산

  • $\phi(D_i) - \phi(D_{i-1}) = k^{\prime} = min(k, s)$
    • $\hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1}) = k^{\prime} - k^{\prime} = 0$

• 각 연산의 상각 시간
  • n개의 연산에 대한 최악의 수행 시간 : $O(n)$

이진 카운터

$\phi(D_i) = b_i$

• $b_i$: $\quad$ i번째 연산 종료 후 상태 $D_i$에서 값이 1인 비트의 개수

• Increment 연산의 실제 연산 시간 : 최대 $t_i + 1$
  • 리셋 되는 비트의 개수($t_i$) + 1로 바꾸는 비트의 연산
• 위치 에너지의 변화량
  • $\phi(D_i) - \phi(D_{i-1}) \leq (b_{i-1} - t_i + 1) - b_{i-1} = 1 - t_i$

• 상각 시간
  • $\hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1}) \leq (t_i + 1) + (1 - t_i) = 2$
  • n번 연산의 최악의 수행 시간 : $O(n)$

---

5. 동적 테이블을 분석해보자

저장된 객체가 늘어남에 따라 테이블의 크기가 커지는 테이블

• 테이블의 확장 -> 테이블의 크기를 늘리는 과정

동적 테이블에 데이터를 삽입하는 경우 수행 시간?

• 이미 사용하던 테이블의 2배 공간을 할당하고,
  기존 객체들을 새 공간에 복사한다.
  • 특징
    • 삽입 연산만 수행할 경우, 항상 테이블의 절반 이상이 사용됨.

Table-Insert(T, x) {
	if size[T} == 0 {
    	table[T]에 1개까리 공간을 할당;
        size[T] = 1;
    }
    
    if num[T] == size[T] {
    	temp = 크기가 2*size[T]인 새로운 공간 할당;
        table[T]에 있던 객체들을 temp에 삽입;
        table[T]의 공간을 반환(free);
        table[T] = temp;
        size[T] = 2 *size[T];
    }
    
    table[T]에 x를 삽입;
    num[T] = num[T] + 1
}

// num[T] : 들어있는 객체의 수

기존 분석

• 최악의 경우 1번의 삽입 연산 : $O(n)$

  • i번째 삽입에서 테이블이 꽉 찬 경우 기존 테이블에서 i-1 객체들을 옮기고,
    1개의 객체를 추가 -> $c_i = i$

• n번의 삽입 연산의 시간 복잡도 : $O(n^2)$

합계 분석

• n번의 삽입 연산

  • $\displaystyle\sum_{i=1}^{n}{c_i}\leq n + \displaystyle\sum_{j=1}^{\lfloor{lgn}\rfloor}2^j < n + 2n = 3n$

• 삽입 연산의 상각 시간 : $3n / n = 3$ -> $O(n)$

회계 방법

• 삽입 연산의 상각 시간 : 3원

  • 1원 : 자신을 삽입할 때 사용
  • 1원: 테이블 확장 시 자신을 새로운 테이블로 이동할 때 사용
  • 1원: 기존 테이블에 있었던 다른 1개의 객체를 옮기는 데 사용

• 확장 직후 테이블의 크기 m

  • 객체의 수는 m/2 이며, 모든 상각 시간을 소비한 상태
  • 객체가 삽입될 때마다 1원은 자신의 삽입을 위해 소비
    • 1원: 다음 확장을 위해 자신이 저장
    • 1원: 저장된 상각 시간이 0인 객체에 저장

• m/2번 삽입

  • m개의 모든 객체가 1원을 가짐
  • 2m으로 확장/이동 가능

• 삽입 연산의 상각 시간 -> $O(n)$

위치 에너지 방법

• $\phi(T) = 2 * num[T] - size[T]$

  • 테이블 확장 직후 $num[T] = size[T] / 2$ -> $\phi(T) = 0$
  • 테이블이 꽉찬 경우 $num[T] = size[T]$ -> $\phi(T) = num[T]$

• $num_0 = 0$, $size_0 = 0$, $\phi_0 = 0$

  • i번째 연산에 의해 테이블이 확장되지 않은 경우 : $size_i = size_{i-1}$
    • $\hat{c_i} = c_i + \phi_i - \phi_{i-1}\\ =1 + (2 * num_i - size_i) - (2 * num_{i-1} - size_{i-1})\\ = 1 + (2 * num_i - size_i) - (2 * num_i - 1) - size_i)\\ = 3$
      
      
  • i번째 연산에 의해 테이블이 확장되지 않은 경우
    • $size_i = 2 * (num_i - 1)$, $\quad$ $size_{i-1} = num_{i-1} = num_i - 1$
    • $\hat{c_i} = c_i + \phi_i - \phi_{i-1}\\ =num_i + (2 * num_i - size_i) - (2 * num_{i-1} - size_{i-1})\\ = num_i + (2 * num_i - 2 * (num_i - 1)) - (2 * num_i - 1) - (num_i - 1))\\ = 3$

• 삽입 연산의 상각 시간 : 3 -> $O(n)$

---