분할 상환 분석

컴퓨터 과학에서, 분할 상환 분석 (amortized analysis)은 주어진 알고리즘의 시간 복잡도나 프로그램을 수행하는데 소요되는 시간 또는 메모리 같은 자원 사용량을 분석하기 위해서 사용하는 기법이다.알고리즘을 분석할 때에 각각의 연산마다 최악의 경우를 따져본다는 것은 굉장히 힘든 일이기 때문에, 이를 쉽게 해결하기 위해 분할 상환 분석이라는 방법론이 나오게 되었다.

어떠한 임의의 알고리즘에 대해서, 어떤 연산은 자원적 측면에서 상당한 비용을 소모할 수 있지만, 반면 다른 연산은 그렇게 고비용을 소모하지 않을 수 있다. 분할상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하는 기법이라 하겠다. 이것은 다른 종류의 입력, 입력의 길이, 이 알고리즘의 성능에 영향을 미치는 다른 요인들을 전부 고려한다. 수행된 모든 연산에 대해 자료구조 연산만의 어떤 시퀀스를 수행하는데 필요한 시간의 평균을 구한다. 비록 그 시퀀스에서 하나의 연산비용이 비싸더라도, 그 일련의 연산에 대해 평균을 구하면 연산 하나의 평균 비용이 작다는 것을 분할 상환 분석을 이용해 보일 수 있다. 분할 상환 분석은 확률이 포함되지 않으므로 평균비용 분석과는 다르다. 분할 상환 분석은 최악의 경우에도 각 연산의 평균 수행성능을 보장한다.

역사

분할 상환 분석은 총계분석(aggregate analysis)이라는 기법으로부터 유래되었다. 하지만 현재는 총계분석이 분할 상환 분석에 포함되어있다. 이 기법은 1985년 Robert Tarjan의 논문 “분할상환 계산 복잡도(Amortized Computational Complexity)”에서 처음으로 소개되었다. 이 논문에서는 기존에 흔히 사용되던 확률론적 방식보다 유용한 형태의 분석 방법론이 필요하다는 점을 시사하고 있다. 처음에 분할상환(Amortization) 방식은 이진 트리같은 자료구조를 분석할 때 매우 한정적으로 사용되었다. 그러나 지금은 다른 자료구조나 알고리즘을 분석할 때 분할 상환 분석을 매우 흔하게 사용하고 있다.

방법

이 방법은 어떤 연산의 시리즈가 가능한지에 대한 지식을 필요로 한다. 연산들 사이에서도 사라지지 않고 계속 유지되는 상태를 가지는 자료 구조를 가지는 경우가 대부분이다. 기본적인 아이디어는 이것이다. Worst case 연산은, worst case(최악의 경우)가 긴 시간동안 다시는 일어나지 않도록 상태를 변경할 수 있다는 것이다. 그러므로 이는 비용을 “분할상환”하는 것이다. 분할상환 분석을 수행하는 방법은 일반적으로 세 가지가 있다. 총계 방식(aggregate method), 회계 방식(accounting method), 잠재비용 방식(potential method)이다. 이 세 가지 방식이 만들어내는 답은 모두 동일하다. 이들의 활용성 차이는 주로 상황에서 비롯되며, 개인적 선호의 차이다.

• 총계분석에서는 모든 n에 대해 n개 연산들의 어떤 시퀀스는 최악의 경우 전체적으로 T(n)의 시간 복잡도를 가짐을 보인다. 따라서 최악의 경우 연산당 평균 비용또는 분할상환비용은 일련의 n 연산 수행에 소요되는 전체 비용에 대해, 상위 경계값을 T(n)으로 결정하고, 분할상환 비용을 T(n) / n 이라고 계산한다. 이때 전체 일련의 연산에 여러종류의 연산이 있을지라도 이런 분할상환 비용은 모든 연산에 동일하게 적용됨을 주의해야한다.
  

• 총계 분석의 예로서 이진카운터 증가를 통해 들 수 있다. 0부터 수를 세어가는 k비트 이진 카운터의 증가시키기 문제를 살펴보면, 카운터로는 비트의 배열인 A[0..k-1]을 사용할 것이다. 이때 A.length = k다. 카운터에 저장되는 2진수 x는 최하위 비트가 A[0]에, A[k-1]에 위치하므로 x=(i=0에서 k-1까지)A[i]*2ⁱ이 된다. 초기값은 x=0이므로 i=0,1,…,k-1에 대해 A[i]=0이 된다. 1을 카운터의 값에 더하기 위해서 다음 절차를 사용한다.
  
  

방법

INCREMENT(A)
1 i = 0
2 while i < length[A] and A[i] = 1
3 do A[i] 0
4 i = i + 1
5 if i < 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<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/2ⁱ]번 반전되게 한다. 이때 i>=k인 비트A[i]는 존재하지 않으므로 반전할 수 가 없다. 따라서 이 시퀀스에서 뒤집히는 총횟수는 2n이다. 그러므로 초기값 0을 가지는 카운터에 대한 n개의 INCREMENT 연산의 시퀀스에서 최악의 경우 수행시간은 O(n)이다. 이때 각각의 연산에 대한 평균비용, 즉 분할상환 비용은 O(n)/n=O(1)이다.

• 회계 방식(accounting method)은 각 연산에 대한 개별적인 비용 계산을, 이 연산의 즉각적인 수행시간과 미래 연산의 수행시간에 대한 이것의 영향력을 결합하여 계산한다. 보통쓰는 방식은, 수행시간이 짧은 많은 연산에 대해, 작은 증가분을 가지게 하여 “빚”으로 적립한다. 반면 긴-수행시간을 가지는 몇 개 안되는 연산에 대해 이것의 수행시간을 상당한 양 감한다.

• 총계분석과 마찬가지로 이진카운터 증가시키는 방법을 예로 회계방식을 설명할 수 있다. 0부터 시작하는 이진 카운터의 INCREMENT 연산을 분석해보면, 앞서 이미 살펴봤듯이 이연산의 수행시간은 반전비트의 개수에 비례한다. 이 비트의 개수는 이예에서 비용으로 쓰인다. 분할 상환 분석을 위해 비트 하나를 1로 만드는데 2달러의 분할 상환 비용을 부과한다고 하자. 비트 하나가 1이 될 때 1달러를 해당비트를 1로 만들기 위한 비용으로 지불하고, 나머지 1달러는 나중에 해당 비트를 0으로 반전 시킬 때 쓰기 위해 그 비트위에 둔다. 이렇게 하면 어떤 순간에도 카운터의 모든 1은 그 자신위에 1달러의 크레딧을 가지고 있게 되고, 그비트를 다시 0으로 만들때는 아무것도 부과할 필요가 없게 된다. 즉, 다시 0으로 만들때는 그 비트위에 있는 1달러로 비용을 지불하면된다. 이저 INCREMENT의 분할상환 비용을 결정할 수 있다. while루프에서 비트를 다시 0으로 만드는 비용은 그 비트위에 놓인 1달러로 지불할 수 있다. INCREMENT 프로시저는 6행에서 최대 하나의 비트를 1로 바꾸므로 INCREMENT연산의 분할상환 비용은 최대 2달러다. 카운터에서 1인 비트의 개수는 결코 음수가 될 수 없으므로, 크레딧의 총합은 항상 0보다 크거나 같다. 그러므로 n개의 INCREMENT연산에 대한 분할 상환비용의 총합은 O(n)이고 이는 실제 비용 총합의 상환이 된다.

• 잠재비용 방법(potential method)은 회계방식과 유사하다. 그러나 연산에 과비용을 초기에 부과하고 나중에 이보다 낮은 값으로 청구하여 이를 보상한다. 미리 지불한 작업을 자료구조에서 특정 객체들과 함께 저장되는 선불 크레딧의 형태로 표현하는 대신, 분할상환 분석의 잠재비용방법은 미리 지불한 작업을 향후의 연산들의 비용을 지불하기 위해 사용될 수 있는 “잠재적 에너지”또는 단순히 “잠재비용”의 형태로 표현한다. 자료 구조의 특정 객체 보다는 자료구조 전체에 대한 잠재 비용을 부여한다. 잠재 비용 방법은 다음과 같이 동작된다. 먼저 초기의 자료구조 D₀에서 시작하여 n개의 연산을 수행한다. i=1,2,…,n에 대해 c_i는 i번째 연산의 실제 비용을, Di는 자료구조 D_i-1에 i번째 연산을 적용한 결과로 만들어진 자료구조를 나타낸다. 잠재적 비용함수 Ф는 각 자료구조 Di를 실수 Ф(Di)에 대응시키는데, 그 숫자는 자료구조 D_i와 연관된 잠재비용(potential)이다. 잠재비용 함수 Ф에 대한 i번째 연산의 분할상환비용은 각연산들의 분할 상환 비용은 실제 비용에 그연산으로 인한 잠재 비용의 변화를 더한 값이다.

• 잠재 비용 방법의 예로서 앞서 설명한 이진카운터 증가에 대해서 얘기할 수 있다. 이번에는 i번째 INCREMENT 연산을 수행한 후의 카운터 잠재비용은 bi이고 이값은 i번째 연산 이후의 카운터에서 1의 개수로 정의한다. ICREMENT연산이 t_i개의 비트를 0으로 재설정했다고 가정하면, 재 설정된 t_i개의 비트들 외에 최대 한 개의 비트가 1로 더 설정될 수 있으므로 이 연산의 실제 비용은 최대 t_i+1이 된다. b_i=0이라면 i번째 연산은 모든 k개의 비트를 재설정하므로 b_i-1=t_i=k가 된다. bi>0이면, b_i=b_i-1-t_i+1이다. 어느 경우라도 b_i<=b_i-1-t_i+1이고 잠재 비용의 차이는 1-t가 되며, 분할 상환비용은 2가 된다. 카운터가 0에서 시작했다면 Ф(D₀)=0이 된다. 모든 i에 대해 Ф(D_i)>=0이므로 연속된 n개의 INCREMENT 연산의 총 분할상환 비용은 실제 총비용의 상한이고 n개의 INCREMENT연산의 최악의 경우의 비용은 O(n)이다.

동적 배열

동적 어레이에서 Push 연산에 대한 분할상환 분석법

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)으로 한다.

참고 문헌

• Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press. pp. 20,141.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7