분할 상환 분석
방법

이 방법은 어떤 연산의 시리즈가 가능한지에 대한 지식을 필요로 한다. 연산들 사이에서도 사라지지 않고 계속 유지되는 상태를 가지는 자료 구조를 가지는 경우가 대부분이다. 기본적인 아이디어는 이것이다. 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]*2i이 된다. 초기값은 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/2i]번 반전되게 한다. 이때 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)은 회계방식과 유사하다. 그러나 연산에 과비용을 초기에 부과하고 나중에 이보다 낮은 값으로 청구하여 이를 보상한다. 미리 지불한 작업을 자료구조에서 특정 객체들과 함께 저장되는 선불 크레딧의 형태로 표현하는 대신, 분할상환 분석의 잠재비용방법은 미리 지불한 작업을 향후의 연산들의 비용을 지불하기 위해 사용될 수 있는 “잠재적 에너지”또는 단순히 “잠재비용”의 형태로 표현한다. 자료 구조의 특정 객체 보다는 자료구조 전체에 대한 잠재 비용을 부여한다. 잠재 비용 방법은 다음과 같이 동작된다. 먼저 초기의 자료구조 D0에서 시작하여 n개의 연산을 수행한다. i=1,2,…,n에 대해 ci는 i번째 연산의 실제 비용을, Di는 자료구조 Di-1에 i번째 연산을 적용한 결과로 만들어진 자료구조를 나타낸다. 잠재적 비용함수 Ф는 각 자료구조 Di를 실수 Ф(Di)에 대응시키는데, 그 숫자는 자료구조 Di와 연관된 잠재비용(potential)이다. 잠재비용 함수 Ф에 대한 i번째 연산의 분할상환비용은 각연산들의 분할 상환 비용은 실제 비용에 그연산으로 인한 잠재 비용의 변화를 더한 값이다.
잠재 비용 방법의 예로서 앞서 설명한 이진카운터 증가에 대해서 얘기할 수 있다. 이번에는 i번째 INCREMENT 연산을 수행한 후의 카운터 잠재비용은 bi이고 이값은 i번째 연산 이후의 카운터에서 1의 개수로 정의한다. ICREMENT연산이 ti개의 비트를 0으로 재설정했다고 가정하면, 재 설정된 ti개의 비트들 외에 최대 한 개의 비트가 1로 더 설정될 수 있으므로 이 연산의 실제 비용은 최대 ti+1이 된다. bi=0이라면 i번째 연산은 모든 k개의 비트를 재설정하므로 bi-1=ti=k가 된다. bi>0이면, bi=bi-1-ti+1이다. 어느 경우라도 bi<=bi-1-ti+1이고 잠재 비용의 차이는 1-t가 되며, 분할 상환비용은 2가 된다. 카운터가 0에서 시작했다면 Ф(D0)=0이 된다. 모든 i에 대해 Ф(Di)>=0이므로 연속된 n개의 INCREMENT 연산의 총 분할상환 비용은 실제 총비용의 상한이고 n개의 INCREMENT연산의 최악의 경우의 비용은 O(n)이다.