분할상환분석

컴퓨터 공학에서, 분할상환분석 (amortized analysis)은 주어진 알고리즘의 시간 복잡도나 프로그램을 수행하는데 소요되는 시간 또는 메모리 같은 자원 사용량을 분석하기 위해서 사용하는 기법이다.알고리즘을 분석할 때에 각각의 연산마다 최악의 경우를 따져본다는 것은 굉장히 힘든 일이기 때문에, 이를 쉽게 해결하기 위해 분할상환분석이라는 방법론이 나오게 되었다.
어떠한 임의의 알고리즘에 대해서, 어떤 연산은 자원적 측면에서 상당한 비용을 소모할 수 있지만, 반면 다른 연산은 그렇게 고비용을 소모하지 않을 수 있다. 분할상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하는 기법이라 하겠다. 이것은 다른 종류의 입력, 입력의 길이, 이 알고리즘의 성능에 영향을 미치는 다른 요인들을 전부 고려한다. 
수행된 모든 연산에 대해 자료구조 연산만의 어떤 시퀀스를 수행하는데 필요한 시간의 평균을 구한다. 비록 그 시퀀스에서 하나의 연산비용이 비싸더라도, 그 일련의 연산에 대해 평균을 구하면 연산 하나의 평균 비용이 작다는 것을 분할 상환 분석을 이용해 보일 수 있다. 분할 상환 분석은 확률이 포함되지 않으므로 평균비용 분석과는 다르다. 분할 상환 분석은 최악의 경우에도 각 연산의 평균 수행성능을 보장한다.
역사.
분할상환분석은 총계분석(aggregate analysis)이라는 기법으로부터 유래되었다. 하지만 현재는 총계분석이 분할상환분석에 포함되어있다. 이 기법은 1985년 Robert Tarjan의 논문 “분할상환 계산 복잡도(Amortized Computational Complexity)”에서 처음으로 소개되었다. 이 논문에서는 기존에 흔히 사용되던 확률론적 방식보다 유용한 형태의 분석 방법론이 필요하다는 점을 시사하고 있다. 처음에 분할상환(Amortization) 방식은 이진 트리같은 자료구조를 분석할 때 매우 한정적으로 사용되었다. 그러나 지금은 다른 자료구조나 알고리즘을 분석할 때 분할상환분석을 매우 흔하게 사용하고 있다. 
방법.
이 방법은 어떤 연산의 시리즈가 가능한지에 대한 지식을 필요로 한다. 연산들 사이에서도 사라지지 않고 계속 유지되는 상태를 가지는 자료 구조를 가지는 경우가 대부분이다. 기본적인 아이디어는 이것이다. Worst case 연산은, worst case(최악의 경우)가 긴 시간동안 다시는 일어나지 않도록 상태를 변경할 수 있다는 것이다. 그러므로 이는 비용을 “분할상환”하는 것이다.
분할상환 분석을 수행하는 방법은 일반적으로 세 가지가 있다. 총계 방식(aggregate method), 회계 방식(accounting method), 잠재비용 방식(potential method)이다. 이 세 가지 방식이 만들어내는 답은 모두 동일하다. 이들의 활용성 차이는 주로 상황에서 비롯되며, 개인적 선호의 차이다.
방법.
 INCREMENT(A)
 1 i = 0
 2 while i &lt; length[A] and A[i] = 1
 3 do A[i] 0
 4 i = i + 1
 5 if i &lt; length[A]
 6 then A[i] = 1
또한 오른쪽 그림은 초기값인 0에서 시작해 16번 증가시켜 16으로 끝나게 하면 카운터에 어떤변화가 일어나는지를 보여준다. 2~4행의 while 루프에서 반복의 처음 부분에서 i위치에 매번 1이 더해진다. A[i]가 i라면 i를 더하는 것은 i위치의 1을 0으로 반전시키고 자리올림을 하나 발생시켜 루프의 다음 번 반복에서 i+1위치에 다시 i를 더하게 된다. A[i]=0인 경우는 while루프가 끝나고, i&lt;k인 경우 6행은 위치 i에 0을 1로 반전시켜 1을 더한다. 그러므로 INCREMENT연산의 비용은 비트가 반전되는 횟수에 비례한다. 
16번의 INCREMENT연산에 의해 0부터 16까지 변하는 8비트 이진 카운터. 다음값으로 넘어가는 과정에서 값이 반전되는 비트들은 회색으로 표시되었고, 비트를 반전시키는 수행 비용은 오른쪽에 표시되어 있다.
N개 INCREMENT 연산들의 시퀀스에 대해 INCREMENT가 불릴 때마다 모든 비트의 반전되지 않는다는 관찰에 근거해, 최악의 경우 O(n)의 비용을 가지도록 분석을 더 엄격하게 할 수 있다. 그림과 같이 A[0]은 INCREMENT가 불릴때마다 반전된다. 다음 자리인 A[1]은 두번에 한 번 꼴로 반전되며, 초기값은 0을 가지는 카운터에 대한 n번의 일련의 INCREMENT연산은 A[1]을 [n/2]번 반전되게 한다. 마찬가지로 비트 A[i]는 초기값0을 가지는 카운터에 대한 n개의 INCREMENT 연산 시퀀스에서 [n/2i]번 반전되게 한다. 이때 i&gt;=k인 비트A[i]는 존재하지 않으므로 반전할 수 가 없다. 따라서 이 시퀀스에서 뒤집히는 총횟수는 2n이다. 그러므로 초기값 0을 가지는 카운터에 대한 n개의 INCREMENT 연산의 시퀀스에서 최악의 경우 수행시간은 O(n)이다. 이때 각각의 연산에 대한 평균비용, 즉 분할상환 비용은 O(n)/n=O(1)이다.
동적 배열.
Java에서 ArrayList나 C++ std의 vector와 같은 동적 배열이 있다고 하자. 이 배열에는 더 많은 요소가 삽입되면 용량이 그만큼 동적으로 늘어나야 한다. 우선 용량이 4인 동적 배열에서부터 시작한다고 하면, 이 배열에 4개의 요소를 배열 끝에 삽입(pushback)하는 연산은 상수 시간이 소요될 것이다. 그러나 다섯 번째 요소는 자리가 없어 보다 큰 용량을 새롭게 확보한 다음 기존 요소를 옮겨야 하기 때문에 비교적 많은 시간이 소요된다. 용량이 부족할 때 두 배로 용량을 늘린다고 가정하자. 최초 용량이 4이므로 용량이 8인 공간을 확보한 다음 기존 배열에 저장되었던 요소들을 새 배열에 옮기는 작업이 필요하다. 하지만 그 다음부터는 상수 시간이 소요된다. 즉, 상수 비용이 소요되다가 저장된 요소의 개수가 2의 거듭제곱이 되면 O(n)의 비용이 소요된다. 이것을 수학적으로 분석하여 n개의 요소를 동적 배열에 삽입하는 비용을 분할상환분석을 하게 되면 전체 비용은 상수 비용이 된다. 즉, 고비용 연산이 가끔 발생하지만 전체적으로는 비용이 높지 않다는 것을 알 수 있다.
Enqueue 연산(큐에 데이터를 삽입하는 연산)은 입력 어레이에 구성요소를 push하는 연산이다. 이 연산은 입력 또는 출력의 길이에 종속되지 않는다. 그러므로 수행시간은 상수이다.
그러나, dequeue 연산(큐에서 데이터를 빼내는 연산)은 보다 복잡하다. 만일 출력 어레이가 이미 그 안에 몇 개의 구성요소를 보유하고 있다면, dequeue 연산의 수행은 상수시간이다. 그렇지 않다면 dequeue연산은 O(n) 이 소요되는데 입력 어레이에서 출력 어레이로 모든 구성요소를 더해야 하기 때문이다. 여기서 n 은 입력 어레이의 현재 길이이다. 입력 어레이에서n 개의 구성요소를 카피한 후, n번의 dequeue연산을 수행할 수 있다. 이때 각각의 dequeue연산은 상수시간이 소요된다. 이 작업은 출력 어레이가 다시 빈 상태가 되기 전까지 수행가능하다. 그러므로, n번의 dequeue연산을 수행하는데 O(n)의 시간만이 소요되며, 이것은 각 dequeue연산의 분할상환 시간이 O(1)임을 의미한다.
또 다른 방식으로, 우리는 해당 아이템에 대한 앞서의 enqueue 연산을 수행하기 위해 입력 어레이에서 출력 어레이로 아이템을 카피하는데 드는 비용을 부과할 수 있다. 이 부과 방식은 enqueue에 대한 분할상환 시간은 두배로 만들지만, dequeue에 대한 분할상환시간은 O(1)으로 한다.