(간단) 분할 상환(amortized) 분석 (+확률적 분석)

 

 

 

개요

 

알고리즘이나 자료 구조의 성능을 볼 때 amortized analysis란 단어를 많이 보게 된다. 이걸 한국어로 번역하면 분할 상환 분석이라는 생소한 단어가 나와 헷갈리는데, 간단히 말하면...

성능을 분석함에 있어서 "N개의 시퀀스를 수행할 때의 평균 시간을 측정했다." 라는 의미이다.

 

왜 이러냐? dynamic array를 한번 생각해보자. dynamic array는 capacity가 꽉 찬 상태에서 add가 일어날 경우, 흔히 doubling 이라 불리우는 비싼 연산을 수행한다. 따라서 dynamic array의 Add 연산의 시간 복잡도는 얼마인가? 라고 묻는다면 대부분의 경우에는 O(1)이겠지만 doubling이 일어날 때는 O(n) (n은 현재 array에 있는 요소의 갯수)이라고 할 수 있다. 그렇다면 dynamic array의 add연산의 "일반적인" 시간복잡도는 얼마라고 말해야 할까?

 

분할 상환 분석

 

위 문제를 분할 상환 분석으로 풀어보면 쉽다. 

 

dynamic array에 총 N개의 아이템을 연속으로 넣는 경우를 가정해보자.(편의상 N은 2의 거듭 제곱이라 하자) 그리고 이것을 단순히 새로운 요소를 더할 때와, doubling을 할 때로 분리해보자.

 

• 단순히 요소를 더할 때의 총 시간은 N이다. 
• 그리고 doubling을 수행할 때의 총 연산은 ... 1+2+4+8+...+N/2+N 이다. 그리고 이것은 2N보다 작다.

 

 

 

그렇다면 dynamic array에 총 N개의 아이템을 넣을 때 총 연산시간은 (N+2N) = 3N 보다 작다.

 

따라서 1개의 요소를 add할 때의 평균 시간은 3N/N = 3으로, 일반적으로 O(1)이라 표기하는 상수 시간 복잡도를 갖게 된다.

 

분할 상환 분석법에서는 크게 회계법과 포텐셜법이란 걸 많이 쓴다.

 

 

확률적 분석(probabilistic analysis)

 

확률적 분석은 입력이 어떤 확률 분포에 따라 이뤄진다고 가정하에 이뤄진다. 간단히 말하면 성능의 확률적 "기댓값"을 표현한다고 이해할 수 있다.

 

이런 방법은 Quick Sort의 성능을 표현할 때 자주 쓴다. Quick Sort는 최악의 경우 $O(n^2)$의 시간복잡도를 갖지만, Pivot을 (균등한)무작위로 선택한다고 가정하면 $O(n log{n})$의 시간복잡도 기대할 수 있다.