17. Amortized Analysis

분할 상환 분석에서는 전체 연산이 수행된 뒤 그 연산의 평균 수행 시간을 분석한다. 이는 확률적 분석과는 다른데, 분할 상환 분석은 각 연산의 최악의 경우에 대한 평균 수행 시간을 보장하는 분석이다.

17.1. Aggregate analysis

집합 분석에서는 모든 n에 대해 n개의 연산들이 총 T(n) 시간을 소모해서, 최악의 경우 평균 수행 시간 (분할 상환 비용)이 \frac{T(n)}{n}이 됨을 보인다.

Stack operations

스택에 MULTIPOP(S, k) 연산을 추가해 보자. 이는 스택에서 k개의 원소를 빼고, k개보다 원소가 적으면 스택 전부를 빼는 연산이다.

MULTIPOP(S, k)
while not STACK-EMPTY(S) and k > 0
    POP(S)
    k--

수행 시간은 \min(s, k)이다. 최악의 경우 이는 O(n)이므로 PUSH, POP, MULTIPOP 연산을 조합해 n번의 연산을 하면 수행 시간은 O(n^{2})이다. 하지만 이 상한을 더 줄일 수 있다. MULTIPOP 내에 불리는 것을 포함해서, POP이 수행되는 횟수는 PUSH가 수행되는 횟수와 같기 때문이다. 따라서 평균 수행 시간은 \frac{O(n)}{n} = O(1)이 된다. 이는 최악의 경우에 대한 평균 수행 시간임에 유의하자.

Incrementing a binary counter

k비트 이진 카운터를 증가시키는 연산을 고려해 보자.

INCREMENT(A)
i = 0
while i < A.length and A[i] == 1
    A[i] = 0
    i++
if i < A.length
    A[i] = 1

이는 최악의 수행 시간이 \Theta(k)이므로 최초 전부 0인 카운터에 대한 n번의 INCREMENT에 대한 상한은 O(nk)라고 할 수 있을 것이다. 하지만 비트 A[i]는 \lfloor \frac{n}{2^{i}} \rfloor 번만 뒤집히기 때문에 뒤집히는 총 횟수는 \sum_{i=0}^{k-1} \lfloor \frac{n}{2^{i}} \rfloor < 2n이다. 그러므로 최악 수행 시간은 O(n)이고, 평균 최악 수행 시간은 O(1)이다.

17.2. The accounting method

분할 상환 분석에서의 회계법에서는 다른 연산에 대해 다른 비용을 할당한다. 이를 분할 상환 비용이라 한다. 분할 상환 비용이 실제 비용을 넘어설 경우 그 차를 공제로 부과한다. 이는 집합 분석과는 다르며, 할당한 분할 상환 비용이 실제 비용에 대한 상한을 제공함을 보장해야 한다.

Stack operations

위의 스택 연산에 대해서는 비용을 다음과 같이 부과해 분석할 수 있다. PUSH – 2, POP – 0, MULTIPOP – 0. 이 때 분할 상환 비용은 O(n)이고, 위의 비용을 부과했을 때 부분 누적 비용은 항상 실제 비용 이상이므로 이를 통해 실제 분할 상환 비용이 O(n)임을 보장할 수 있다.

Incrementing a binary counter

이진 카운터에 대해서는 비트를 1로 만들 때의 비용을 2로 부과해 분석할 수 있다. 이 때 분할 상환 비용은 O(n)이고, 위의 비용을 부과했을 때 부분 누적 비용은 항상 실제 비용 이상이므로 이를 통해 실제 분할 상환 비용이 O(n)임을 보장할 수 있다.

17.3. The potential method

잠재 법은 회계 법과 비슷하지만 분할 상환 비용과 실제 비용의 차를 자료 구조에서 잠재량으로 보내는 함수인 잠재 함수의 차로 모델링한다.

\hat{c}_{i} = c_{i} + \Phi(D_{i}) - \Phi(D_{i-1})

이 때 전체 분할 상환 비용은 \sum_{i=1}^{n} \hat{c}_{i} = \sum_{i=1}^{n} c_{i} + \Phi(D_{n}) - \Phi(D_{0})이 된다. \Phi(D_{n}) \geq \Phi(D_{0})이 되도록 하면 된다. 보통은 \Phi(D_{0}) = 0, \Phi(D_{i}) \geq 0이 되게 한다.

Stack operations

스택 연산에서는 잠재 함수를 스택 내에 존재하는 원소의 수로 정의하면 된다.

Incrementing a binary counter

이진 카운터에서는 잠재 함수를 카운터 내 1이 된 비트의 수로 정의하면 된다.

17.4. Dynamic tables

할당한 테이블을 효율적으로 동적으로 늘리고 줄이려면 어떻게 할까? 이를 분할 상환 O(1)에 할 수 있다. 부하 인자 \alpha(T)를 테이블의 크기 대 들어간 원소의 수의 비율로 정의하자.

17.4.1. Table expansion

테이블의 확장은 다음과 같이 수행한다.

TABLE-INSERT(T, x)
if T.size == 0
    allocate T.table with 1 slot
    T.size = 1
if T.num == T.size
    allocate new-table with 2 * T.size slots
    insert all items in T.table into new-table
    free T.table
    T.table = new-table
    T.size = 2 * T.size
insert x into T.table
T.num++

이 때 기본적 삽입 연산은 2가지 상황에서 일어난다. 테이블이 확장될 때 기존 테이블 전체의 삽입과 원소 하나의 삽입. 이 때 분할 상환 평균 비용은 3이다.

17.4.2. Table expansion and contraction

부하 인자가 작을 때 테이블을 수축시킬 수 있다. 테이블이 절반 이하로 차 있으면 테이블을 반으로 줄이면 될까? 그렇지 않다. 절반만큼 차 있을 때 삭제-삽입-삭제-삽입 등등을 반복하는 경우를 생각해 보라. 테이블이 1/4 이하로 차 있을 때 테이블을 반으로 줄이면 분할 상환 평균 비용 3이 된다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중