분할 상환 분석 Amortized Analysis

상각(분할 상환) 분석 Amortized Analysis 소개

여기에서 말하는 상각분석이란, 알고리즘의 성능을 분석하는 기법 중 하나로

주어진 연산에서의 worst case 비용을

연산들의 시퀀스 전체에 평균화시켜서 분석하는 방법이다.

 

간단히 말해서,  평균적인 시간 복잡도를 분석하는 방법이다.

 

 

이 방법을 통해 어떤 개별 연산의 비용은 값비쌀 수 있지만, 전체 시퀀스에서의 평균 비용은 낮다는 것을 보여줄 수 있다.

 

스택 기반 알고리즘에서는 이런 분할 상환 분석이 특히 유용하다.

 

여기에서 스택 기반 알고리즘이란, 스택 자료 구조를 사용하여 연산을 관리하는 것을 말한다. (후입선출 LIFO)

 

 

 

예시

사무실에 10인분 분량의 커피 머신이 있다고 치자.

커피 머신이 비어있지 않은 경우 컵에 커피를 붓는 데 10초가 소요된다.

머신이 비어있는 경우 커피를 만드는 데 10분 정도 소요된다.

 

이 때, 커피머신을 10명이 사용할 수 있을 때 시간 복잡도를 구해보자면

worst case는 10명 * 10분으로 100분이 나온다. 하지만 큰 의미 없는 분석 결과이다.

 

분할 분석의 경우는 (10초 * 10명) + (10분 * 1) = 11.67분으로, 각 작업의 평균 성능은 1.16분이다

 

 

 

상각 분석을 위한 방법

우리는 이 방법들을 Stack with Multipop Operation, Incrementing Binary Counter 두 가지 예시를 사용해서 알아볼 것이다.

 

Aggregate analysis

aggregate analysis란, 일련의 n개 operation의 worst case 총 비용 T(n)을 분석해서, 이 비용을 평균화시키는 것으로 상각 비용을 알아내는 방법이다.

따라서 이 경우에 operation 당 상각 비용은 T(n) / n 이다.

 

Aggregate Analysis - Stack with Multipop

우리가 이미 알고있듯이, 스택 연산은

• 스택 S에 element x를 push하는 Push(S,x)연산
  Cost O(1)
• 스택 S의 최상위에 위치한 element를 pop하는 Pop(S)연산
  Cost O(1)
• 스택 S의 최상위에 위치한 element를 k개 pop하는 Multipop(S,k)연산
  Cost O(k)

이렇게 이루어져 있다.

처음에 비어있는 스택에서 일련의 n개 operation 비용을 구해볼 때

Push(S,x)와 Pop(S) 연산으로만 이루어져 있는 경우, < Push, Push, Pop, Push, …, Push, Pop > 이므로

total cost는 theta(n)이다.

 

 

그렇다면 Multipop 연산도 같이 포함된 경우, < Push, Push, Pop, Push, Multipop(2), …, Multipop(3), Pop >

이 때의 cost는 얼마일까?

 

wortst case의 경우 Multipop 연산은 O(n)이므로 (스택이 다 차있을 경우)

total worst case cost는 O(n^2)이다.

하지만 이런 분석 방식은 tight하지 않다.

Multipop은 Pop연산 개수의 선형이기 때문에, 스택이 다 차지 않았을 경우 Multipop(n)의 실제 cost는 O(n)보다 작다.

 

 

여기에서 Aggregate 방식의 분할 상각 분석을 해보면 더 최적의 cost 상한값을 얻을 수 있다.

 

모든 n개 operation의 실제 cost를 합하는 분석 방식을 취해보면, 우리는 스택에 element를 push했을 때만 pop할 수 있다.

 

이렇게 Pop 또는 Multipop 연산의 개수는 최대 Push 연산의 개수가 되고, 분할 상각 cost는 O(1)이 된다.

 

 

 

Aggregate Analysis - Binary Counter

배열 A[0, 1, …, k-1 ]를 counter로 사용해서 0부터 수를 세는 k-bit binary counter를 구현해보자.

 

예를 들어 각 카운터에 표시되는 것에 따라 나타나는 값은 다음과 같다.

 

 

 

 

비트 플립의 횟수는 카운터의 값에 따라 달라질 수 있다.

 

 

이 increment 연산의 비용은 bit가 flip되는 횟수에 비례한다.

worst case는 마지막 줄을 보면 single execution operation이 O(k)를 갖는 것을 볼 수 있다.

하지만 이런 계산은 tight한 upper bound가 아니다.

 

각 비트마다 뒤집는 경우의 수는 정해져있으므로, Aggregate alaysis로 모든 수의 bit flip sequence를 총합하면 2n의 값을 얻을 수 있다.

 

따라서 total cost는 O(n)이라는 값을 얻을 수 있고, Amortized cost per operation은 O(n)/n = O(1)을 구할 수 있다.

 

 

 

 

Accounting method

 

aggregate analysis와 달리, 다른 operation type에 다른 amortized cost를 할당한다.

즉, 각각의 연산에 대해 가상의 비용을 설정한다.

그래서 몇몇개의 연산에는 실제 비용보다 더 청구될 수 있고, 덜 청구될 수도 있다.

 

주의할 점은 다른 비용을 설정한다고 해도, 모든 연산에 대해 일관적인 방식으로 비용을 설정하는 것이다.

 

 

이런 가상의 비용을 기반으로 전체 연산의 평균적인 시간 복잡도를 계산한다. 

 

total amortized cost는 total cost의 상한을 제공하기 위해, 시퀀스의 총 실제 비용보다 커야 한다.

 

 

 

 

Accounting Method - Stack with Multipop

 

stack연산의 실제 비용은

• Push(S,x) = 1
• Pop(S) = 1
• Multipop(S, k) = k (1 ≤ k ≤ n)

 

stack연산의 amortized cost는

• Push(S,x) = 1 + 1(credit) = 2
• Pop(S) = 0
• Multipop(S,k) = 0

 

실제 Push 비용보다 amortized cost가 더 큰 것을 통해 우리는

Push된 element를 Pop하는 데 드는 비용을 미리 지불했다는 것을 알 수 있다.

 

따라서 Pop이나 Multipop에 대한 비용은 0이 된다.

 

 

이렇게 n개의 operation < Push, Push, Push, Push, …, Push, Push> 의 total amortized cost는

worst case에서 O(2n)이 되고

각 연산 당 amortized cost는 O(n)/n = O(1) 이 된다.

 

따라서 total 실제 비용은 O(n)이 된다.

 

 

 

 

Accounting Method - Binary Counter

 

실제 비용

• 0에서 1로 bit flip = 1
• 1에서 0으로 bit flip = 1

 

amortized cost

• 0에서 1로 bit flip = 1 + 1(credit)
• 1에서 0으로 bit flip = 0

 

위 스택과 같은 맥락으로, 1에서 0으로 뒤집는 데에 필요한 비용을 미리 지불했으므로 amortized cost는 항상 실제 비용보다 크다.

n개의 increment operation O(n)의 total amortized cost는

worst case에서 O(2n)이 되고

각 연산 당 amortized cost는 O(n)/n = O(1) 이 된다.

 

따라서 total 실제 비용은 O(n)이 된다.

 

 

 

 

Potential method

 

각 연산별 데이터 구조의 potential energy (Potential)을 분석하는 것이다.

즉, 상태와 연산의 변화에 따라 비용을 분석하는 기법이다.

 

accounting method와 비슷해 보이지만, credit이 potential이다.

amortized cost는 실제 비용 + 연산 동안 변경된 potential만큼 더해준다.

여기에서 D는 i번째 연산 후의 자료구조를 말하고, 각 자료구조의 potential을 더해주는 것이다.

 

potential이 0보다 크면 i번째 연산에서 비용이 과하게 청구되었다는 것이고,

0보다 작으면 적게 청구됐다는 의미이다.

 

 

이런 계산을 통해 total amortized cost를 구해보면

이와 같은 결과를 얻을 수 있다.

 

 

 

 

Potential Method - Stack with Multipop

 

포텐셜 함수는 스택에 있는 elements의 수로 정의될 수 있다.

초기 D값은 0으로, 비어있는 스택을 표현하고

0보다 큰 Di는 i번째 연산 이후의 스택을 나타낸다.

 

amortized cost를 구해보면

• Push(S,x) = 2 = 1 + 1
  여기에서 실제 비용 1, 바뀐 포텐셜 비용 (s+1) - s = 1이다.
• Pop(S) = 0 = 1 - 1
  실제 비용은 1, 바뀐 포텐셜 비용은 (s-1) - s = -1이다.
• Multipop(S,k) = 0 = k - k
  실제 비용은 k, 바뀐 포텐셜 비용은 (s-k) - s = -k이다.

 

 

이 비용들을 보면 accounting method의 amortized cost와 같은것을 확인할 수 있다.

• The total amortized cost O(n)
• The amortized cost per operation O(1)
• The total actual cost O(n)

 

 

 

 

Potential Method - Binary Counter

 

포텐셜은 binary counter중 하나로 (1개) 정의될 수 있다.

 

초기 D값은 counting 하기 전 counter로 나타낼 수 있고

이후의 D는 i번째 연산 이후의 counter 결과로 표현될 수 있다.

 

 

i번째 INCREMENT operation 이후에 0으로 리셋되는 비트를 t라고 할 때, 다음 식이 성립한다.

우리가 구하려는 이 식에서 실제 비용 c는 c ≤ t + 1이고,

 

바뀐 포텐셜 에너지를 구해보면 

 

i번째 포텐셜 에너지는 다음과 같이 구할 수 있다.

 

 

accounting method와 동일하게 amortized cost는 다음과 같다.

 

• The total amortized cost O(n)
• The amortized cost per operation O(1)
• The total actual cost O(n)

 

 

 

 

amortized analysis 예제

 

앞에서 배웠던 amortized analysis의 예제 문제를 통해

• (1) aggregate analysis
• (2) the accounting method
• (3) the potential method

이 방법들을 이해해보자.

 

주어진 데이터 구조에 대해 n번의 연산을 수행한다고 가정해보자.

여기서 i번째 연산의 비용은, 만약 i가 정확히 2의 거듭제곱인 경우 i이고, 그렇지 않으면 1이다.

 

 

Aggregate Analysis

각 연산 당 평균 비용은 3n/n = 3이 되고,

각 연산 당 amortized 비용은 O(n)/n = O(1)이다.

 

 

 

Accounting Method

여기에서 나타나는 amortized cost 3이 의미하는 것은 Dynamic Tables을 말한다.

 

따라서 각 연산 당 amortized cost의 시간복잡도는 O(1)이 되고, total 실제 비용은 O(n)이다.

 

 

 

Potential Method

포텐셜 함수는 이렇게 amortized cost를 상수로 만드는 것으로 정의될 수 있다.

 

위 식에 따라서 각 연산 당 amortized cost는 O(1)이 되고

실제 total 비용은 O(n)이다.