Analysis of Algorithms | Amortized Analysis Introduction

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다. 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

분할상환 분석(Amortized Analysis)

점근적 분석(Asympotic Analysis) 방법에서는 알고리즘의 수행시간의 범위를 포함할 수 있는 합수로 표현하기 때문에 대부분 $O(1)$이고 간혹 $O(n)$이라도 $O(n)$으로 취급하기에 비효율적인 경우가 발생한다. 이 문제를 해결하기 위해 간혹 발생하는 최악의 경우를 구분해서 고려하는 분할상환 분석(Amortized Analysis)를 사용한다.

예를 들어 어떤 해시 테이블이 존재하고 차례로 item을 넣는다고 하자. 테이블의 상태가 full이 될 때마다 해당 테이블을 복사하고 길이가 2배인 새로운 테이블에 넣고서 원래의 테이블은 비운다. 그 과정을 그림으로 표현하면 아래와 같다.

그림에 따르면 테이블이 full 상태가 아닐 경우 단순히 item 1개만 입력하는 과정을 수행하므로 수행시간은 1이다. 그러나 full 상태라면 전체 테이블을 복사한 후 새로운 item 1개를 입력하므로 수행시간은 $2^{log_{2}(n-1)}+1$이 된다.

시간복잡도 T(n) 계산

총계 모델(Aggregate Model)

크기가 n인 해당 테이블을 채우는 작업을 수행하는 중 최악의 케이스는 테이블이 full 상태가 되어 모든 item을 복사하는 단계이고 해당 단계의 시간복잡도는 O(n)이 된다. 그러므로 n번 삽입하는 수행과정 중 최악의 비용을 고려하면 $n\cdot O(n)$으로 전체 시간복잡도는 $O(n^2)$이 된다. 이는 우리가 흔히 말하는 점근적 분석에 따라 도출된 상계에 대한 해답이다. 그러나 n번의 입력과정 전반을 고려하여 엄밀하게 따져보면 모든 입력 과정이 $O(n)$만큼 소요되지 않는다. 그렇기 때문에 점근적 분석방법으로 도출된 상계는 그렇게 타이트하진 않다.

각 단계별 테이블 크기와 비용을 나열하면 아래 표와 같다.

그러므로 단계별로 분할하여 수행시간을 고려하면 $Amortized\ Cost= \cfrac{(1+2+3+1+\cdots)}{n}$이 된다. 문제에서 제시된 과정을 표현하면 단순 입력과정은 n회 발생하고 테이블을 복사하는 과정은 $[log_{2}(n-1)]+1$ 단계마다 발생함을 확인할 수 있다. 수행시간을 단순 입력과정과 테이블을 복사하는 과정으로 구분하면 $\cfrac{1+1+\cdots+1}{n}+\cfrac{1+2+4+\cdots+2^{|log_{2}(n-1)|+1}}{n}$이 된다. 공차가 1보다 큰 등비급수의 합인 $a_1+\cdots+a_{n-1}$은 $a_n$보다 작기 때문에 이 식은 $\cfrac{[n+2n]}{n}\le3$이 성립하며 결국 $O(1)$이 됨을 확인할 수 있다.

회계 모델(Accounting Model)

이 방법에 따르면 item을 입력하는 과정 대부분 테이블의 크기가 일정하지만 간혹 full 상태가 발생함에 따라 item을 새로운 테이블에 옮기는 비용을 산출하여 그 비용(Accounting cost)을 모든 단계에 배분한다. 이렇게 함으로써 간혹 발생하는 불균형을 모든 단계로 분산하여 평준화하는 것이다. 즉, Amortized Cost = Actual cost + Accounting cost이다. 테이블이 full 상태일 때, 크기가 Doubling 된 테이블로 item을 옮기는 비용을 Transferring 비용이라고 하자. item 한 개를 새로운 테이블로 옮길 때 t만큼의 시간이 소요된다고 하면 n개의 원소를 새로운 테이블로 옮기는 시간은 tn이지만 이 값은 현재 n개의 원소를 새로운 테이블로 옮기는 비용이다. 그러므로 이전까지 테이블의 크기가 Doubled된 경우들을 산출해보면 $\cfrac{tn}{2}+\cfrac{tn}{2^2}+\cdots+\cfrac{tn}{2^{[log_{2}(n-1)]+1}}\le tn$이 된다. 그러므로 모든 단계에 걸쳐 full 상태가 됨에 따라 발생하는 Transferring 비용은 항상 $2tn$보다 작다. 즉, 모든 단계에 배분해야 하는 Accounting cost는 $\cfrac{2tn}{n}=2t$이다.

1. 테이블이 full 상태가 아닐 때

   원래 item의 입력시간 1과 Accounting cost를 더하여 Amortized cost는 Actual cost(1)+Accounting cost(2t) = 1+tn이다.

2. 테이블이 full 상태가 되었을 때

   원래 item의 입력시간 1과 Transferring cost를 더하여 Actual cost는 1+tn이 되고 Accounting cost는 기존의 2t와 이전까지 full 상태가 발생했을 때를 대비하여 다른 단계에서 더했던 2t들을 다시 감산하여 2t-tn이 된다. 즉, Amortized cost는 Actual cost(1+tn)+Accounting cost(2t-tn)이 되어 1+2t가 된다.

따라서, 간혹 발생하는 비용을 평준화한 결과 항상 1+2t의 비용이 발생하므로 $O(1+2t)=O(1)$이 된다.

참고자료

1. Analysis of Algorithm | Set 5 (Amortized Analysis Introduction)