Amortized Analysis

계산이론 수업에서 배운 내용 정리. CLRS CH 17.

Amortized Analysis

우리는 일반적으로 어떤 알고리즘을 분석할 때, $O$, $\mathrm{\Theta }$ 같은 asymptotic을 사용해서 분석합니다. 예를 들어, 연산 한번에 $O(n)$ 시간이 들고 그 연산을 $m$번 해야 한다면 전체 시간 복잡도는 $O(nm)$이 될 것입니다.

이 방법은 유용하지만 어떤 알고리즘들은 이렇게 단순하게 분석할 수 없습니다. 대표적인 예시가 C++의 vector (dynamic array)입니다.

vector의 모든 연산을 분석하지는 않더라도, 우리는 일단…

• 맨 뒤에 push하는 연산이 $O(1)$ 시간에 작동하기를 원합니다.
• 맨 뒤에서 pop하는 연산이 $O(1)$ 시간에 작동하기를 원합니다.

이 두 가지는 stack으로도 가능한 일입니다. 그러나…

• 연속한 메모리만 사용하여, 바로 index를 확인할 수 있어야 합니다. stack을 링크드 리스트로 구현하면 위 두가지를 지키기 쉽지만, 대신에 vec[17] 같은 것을 바로 확인할 수가 없습니다. 동적 배열은 이것이 가능해야 합니다.

그런데, 이 두 조건은 뭔가 이상합니다. 배열의 원소들이 연속한 메모리를 점유해야 한다면 계속 push를 하다가 언젠가는 더이상 그 위치의 메모리를 쓸 수 없게 되고, 그러면 모든 원소들을 어딘가로 옮겨야 하므로 그때 들어있는 원소의 개수만큼의 시간이 소요될 것입니다. 그러므로, 연속한 메모리를 점유하기 위해선 반드시 $O(n)$ 시간이 걸리는 push가 존재합니다.

이를 해결하기 위해, vector는 대략 다음과 같은 방법을 씁니다.

• size와 capacity를 분리합니다. size는 진짜 현재 들어 있는 원소의 개수를, capacity는 할당된 메모리를 말합니다.
• 만약 capacity가 다 차지 않았다면 push가 $O(1)$에 기능하게 하는 것은 쉽습니다.
• capacity가 다 찼다면, 현재 모든 원소들을 새로운 곳으로 옮기되, capacity가 현재 크기 +1이 아니라 현재의 두 배가 되게 잡습니다.

이렇게 하면, move 하는 연산이 가끔씩만 일어나기 때문에, 평균적으로는 빠릅니다. 이와 같이, 매 operation의 cost를 생각하는 대신, 여러 operation의 cost를 묶어서 그 평균을 계산하는 방법을 amortized analysis라고 부릅니다.

주의할 점은, amortized analysis는 average case와는 다르다는 점입니다. 알고리즘 분석은 대부분 worst case를 기준으로 하는데 (최근에는 average case도 많이 나오긴 합니다), amortized worst case 도 생각할 수 있습니다. 한국어로 이를 자연스럽게 바꾸자면, “최악의 경우에도 각 연산은 평균 $O(1)$ 에 작동한다” 입니다. “평균적인 경우에 평균 $O(1)$” 이나, “평균적인 경우에 한번당 $O(1)$” 과는 다른 말입니다.

Three frameworks

Amortized analysis를 하는 방법에는 크게 3가지가 있습니다.

Aggregate Method

$n$번의 연산에 걸리는 시간을 모두 더한 다음, $n$으로 나눕니다. 가장 단순한 방법입니다. 이를 앞서 제시한 vector에 적용해 보겠습니다.

벡터에 $n$개의 원소를 집어넣는다고 하겠습니다. $n=2^k$ 일 때는 $2^k$ 의 시간이 들고, 그 외에는 1의 시간이 든다고 가정하면, 전체 시간은 $$T(n)=n+\sum _{k=1}^{{\log }_{2}n}{2}^k$$ 이렇게 될 것입니다. 뒷부분의 $2^k$들의 합을 전부 취하면 $2n$ 이하임을 바로 알 수 있고, 이는 즉 $n$번의 연산이 총합 $3n$ 이상 걸리지 않는다는 것입니다. 따라서 개별 연산은 평균 $O(1)$입니다.

Accounting Method

어떤 연산의 실제 cost와는 별개로, 이 연산의 가격을 조금 넉넉하게 할당한 다음, 비싼 연산을 할 때 앞에 쟁여놓은 (?) 여분을 가져다 쓴다고 생각하는 방법입니다.

역시 vector에 적용해 보겠습니다. $n$개의 원소를 집어넣는데, 개당 보통은 1이 들지만 일단 3이 든다고 생각하겠습니다. Expansion 직후에 남은 credit은 고려하지 않고, 지금 $2^k$개의 원소가 들어있는 테이블에 추가로 $n$개를 집어넣는다고 생각합니다. 이때, 개별 연산을 넉넉하게 3의 시간이 든다고 하면, $2n$어치가 남습니다. 예외적으로, $n$개를 집어넣다가 원소가 $2^{k+1}$ 개가 되면 연산이 실제로는 $2^{k+1}$ 시간이 들게 되는데, 이는 우리가 가정한 cost 3보다 큽니다.

그러나, 여기까지 오는 길에 우리는 실제로는 1만큼이 걸리는 연산을 3이라고 넉넉하게 잡으면서 $2^k$ 개를 넣어 왔습니다. 즉 $2^{k+1}$ 만큼 여분의 credit이 남았을 것입니다. 이를 이용하여 테이블 확장에 필요한 시간을 지불한다고 생각할 수 있습니다. 이와 같이 적당한 여분을 둔 다음 이를 나중에 사용하는 방법을 Accounting method라 합니다.

이 방법은 약간 애매한데, 처음에 3이라는 애매한 숫자를 어떻게 잡을지를 알려면 대충 평균적인 연산의 가격을 찍을 수 있어야 합니다. 그래서 증명하기는 어렵지 않지만, 처음 수치를 제시하는 조금…뭐랄까요, 비정형적입니다.

Potential Method

이 글을 쓰게 된 이유이자, amortized analysis의 핵심입니다.

이 자료구조의 상태를 나타내는 어떤 potential function $\varphi (T)$ 를 생각합니다. 즉, 현재 벡터의 상태를 수치로 환산한다는 것입니다. 이때, 다음과 같은 조건을 만족하고자 합니다.

• 초기 상태에 0. 즉, $\varphi (T_0)=0$
• 언제나 $\varphi (T_i)\ge 0$. (사실 2번 조건은 조금 relax할 수 있지만, 아무튼…)

이제, 각 연산은 cost가 들 뿐만 아니라, potential function을 변화시킬 것입니다. $i$번째 연산이 potential function을 변화시키는 양을 $\mathrm{\Delta }{\varphi }_i$라 쓰면, 다음이 성립합니다. $${\varphi }_n={\varphi }_0+\mathrm{\Delta }{\varphi }_1+\cdots \mathrm{\Delta }{\varphi }_n$$ 어떤 연산의 amortized cost $c_i$를, 실제 cost $r_i$에 potential function 변화량 $\mathrm{\Delta }{\varphi }_i$를 더한 값으로 생각합니다. 즉, $c_i=r_i+\mathrm{\Delta }{\varphi }_i$.

$c_i$의 총합과 $r_i$의 총합을 비교하면… $$\sum c_i=\sum r_i+\sum \mathrm{\Delta }{\varphi }_i=\sum r_i+{\varphi }_n-{\varphi }_0\ge \sum r_i$$ (${\varphi }_n\ge {\varphi }_0=0$ 이므로) 따라서, $c_i$의 합을 어느 이하로 바운드를 잡아주면 이 바운드가 실제 cost의 합의 bound가 됩니다.

vector에 적용해 보겠습니다. vector의 potential은 현재 들어있는 원소의 개수 $n_i$ 와 vector의 크기 $s_i$에 대해, $2n_i-s_i$ 로 정의하기로 하겠습니다. 초기에 벡터에 들어있는 원소가 없을때 약간 정의가 애매한데, 초기의 size를 0으로 잡으면 이 potential function이 위 조건 두개를 만족함을 알 수 있습니다.

• $r_i$가 size를 변화시키지 않는 연산이라면, 실제 cost가 1이고 potential의 변화는 $s$가 그대로인 채 $n$이 1만큼 증가하여 $\mathrm{\Delta }\varphi =2$ 입니다.
• $r_i$가 size를 변화시킨다면, $n$은 1만큼 증가하는데 $s$가 2배로 증가합니다. 이전에 $s_{i-1}=n_{i-1}$ 이었을 것이므로, $$(2n_i-s_i)-(2n_{i-1}-s_{i-1})=(2n_{i-1}+2-2s_{i-1})-s_{i-1}=2-s_{i-1}$$ 따라서 $\mathrm{\Delta }\varphi$ 는 $2-s_{i-1}$ 입니다. 그런데, 옮겨야 하는 원소는 $s_{i-1}$ 개이고, 새로 추가하는 1개를 고려하면 실제 cost는 $1+s_{i-1}$ 입니다. 따라서 $c_i=3$입니다.

이 두 경우 모두 amortized cost가 $O(1)$ 이므로 전체도 amortized $O(1)$ 입니다.

일반적으로 $c_i$의 합에 대해 뭔가를 논의하는 것이 쉽도록 $\varphi$를 잘 잡는 것을 목표로 합니다. 이 경우는 worst case에도 연산이 한가지밖에 없어서 aggregate로 쉽게 풀 수 있지만, 여기에 delete만 추가하더라도 aggregate로는 분석하기가 굉장히 어렵습니다.

Dynamic table

만약 위 vector에 pop도 지원해야 한다면 어떨까요? 사실 pop은 많이 하더라도 메모리를 침범하지 않아서 그대로 하더라도 시간 복잡도는 유지됩니다. 그런데, 100만개를 넣었다가 다시 100만개를 뺐는데 vector가 그대로 100만칸을 먹고 있는 것은 뭔가 모양새가 나쁩니다. 이 경우에는 table의 크기에 비해 실제 원소의 개수 - 이를 load factor 라고 부릅니다 - 가 너무 나빠서, 메모리 효율이 떨어지는 경우입니다.

이를 해결하기 위해서는, 원소의 개수가 1/2 이하가 되면 테이블 크기를 반으로 줄이는 방법을 가장 먼저 생각할 수 있습니다. 그러나 이렇게 하면, 원소의 개수를 1/2개 근처로 유지하면서 push와 pop을 반복하면 테이블의 축소와 확대가 여러번 일어나게 만들 수 있고, 축소/확대는 $O(n)$ 연산이므로 비싼 연산을 가끔씩만 한다는 사실을 이용한다 는 amortized 의 개념이 적용되지 않습니다. 실제로 이러면 worst case amortized $O(n)$ 이 됩니다. (Amortized는 average를 내기는 하지만, average case (축소/확대가 랜덤하게 발생) 를 분석하는 것이 아니라 worst case의 average도 분석할 수 있음을 잘 보여주는 사례입니다)

Load factor를 적절히 유지하면서 amortized $O(1)$을 적용하는 방법은, load factor를 최하 1/4까지 허용하여, 1/4 이하가 되면 테이블 크기를 반으로 줄이는 것입니다.

이 방법이 amortized complexity $O(1)$ 을 유지한다는 것을 aggregate 같은 방법으로 보이려고 하면 매우 어렵습니다. 어떤 sequence로 연산이 주어지더라도 - 라는 개념을 적용하기가 어렵기 때문입니다. 대신에 potential function으로 다음과 같은 함수를 생각하면 $$\varphi =max(2n_i-s_i,s_i/2-n_i)$$ 이를 잘 이용하여 amortized cost를 바운드할 수 있습니다. 위 함수는 load factor가 1/2 이상일 때와 미만일 때 구간에 따라 정의된 함수이므로, 총 8가지 경우를 분석해야 합니다.

• load factor 1/2 (이상, 이하) 일 때 이를 유지하면서 삽입/삭제하는 경우 4가지
• load factor 1/2 이하에서 이상으로, 이상에서 이하로 넘어가는 삽입과 삭제 2가지
• load factor 1/4 이상에서 이하로 떨어져서 축소를 시행하는 삭제
• load factor 1에서 추가 삽입으로 인해 확대를 시행하는 삽입 정말 하나씩 다 분석하는 것이므로 자세한 과정은 생략합니다.

Application

복잡한 연산을 다양하게 수행하는 자료구조에서 매우 유용합니다.

• 피보나치 힙 (예전에 제가 쓴 글도 여기 있습니다.) 을 이용하여 다익스트라 알고리즘의 시간 복잡도를 $O(V\log V)$ 로 내리기
• Splay Tree 와 같은 자료구조의 복잡도 분석.

---