이번 포스트에서는 분할 상환 분석(amortized analysis)에 대해서 알아보도록 하겠습니다. 자료 구조나 알고리즘 수업을 들으셨다면 분명 한 번쯤은 들어 보신 개념일 것입니다. 개인적으로는 자료 구조 수업 시간에 처음 분할 상환 분석에 대해서 배웠었는데요, 당시에는 잘 이해하지 못했던 기억이 있습니다. 아마도 많은 분들이 도대체 분할 상환 분석이 무엇이고, 이것이 어째서 중요한지에 대해 당시의 저처럼 이해하지 못하실 것으로 생각하는데요. 이 포스트를 통해서 그 이유를 알아 가셨으면 하는 바람입니다.
서론: 어느 회사의 커피
이 예제는 제가 대학생일 때 자료 구조 수업에서 교수님께서 분할 상환 분석을 설명하기 위하여 소개한 것입니다. 솔직히 처음 들을 당시에는 제대로 이해하지 못했습니다만, 지금 돌이켜 보니 이 예제가 분할 상환 분석을 가장 효과적으로 표현하는 예제 중 하나였다고 생각합니다.(역시 교수님!) 여러분들께도 공유하고자 이를 가지고 왔습니다.
어느 회사에 크기가 제법 큰 커피 만드는 기구가 있다고 합시다. 회사 생활의 고단함을 위로하고자 중간중간 사원들은 커피를 마시러 옵니다. 만약 기구에 남은 커피가 있다면 컵에 따르기만 하면 되고, 이는 10초면 충분합니다. 반대로 남은 커피가 없다면 기구를 사용해 커피를 만들어야 하며, 이를 위해서는 10분의 시간이 필요합니다. 대신 크기가 제법 크기 때문에 한번에 10인분의 커피를 만들 수 있습니다. 커피를 마시러 오는 모든 사람들이 만약 커피가 남아 있다면 그냥 커피를 따라서 가고, 남아 있지 않다면 10인분의 커피를 만든 후에 따라간다고 합시다. 이때, 과연 사원들이 커피를 가져오기 위해서 얼마나 긴 시간을 소모해야 할까요?
운이 좋아 남은 커피가 있다면 10초만에 커피를 갖고 올 수 있습니다. 하지만 운이 나쁘다면 꼼짝 못하고 10분 정도가 걸릴 것입니다. 그러므로 "최악의 경우" 10분 정도의 시간이 걸린다고 말할 수 있습니다. 그런데 과연, 이렇게 분석하는 것이 각 사원들이 커피를 갖고 오는 시간을 잘 반영하고 있다고 볼 수 있을까요?
예를 들어, 100명의 사원이 커피를 가지러 갔다고 합시다. 위 분석을 통해 이끌어 낼 수 있는 것은 아무리 길어도 1,000분 정도의 시간이면 모든 사원이 커피를 마실 수 있다는 것이죠. 하지만 실제로 그 정도의 시간이 걸렸을까요? 아닙니다. 100명의 사원 중에서 커피를 만들어야 했던 사람은 10명뿐입니다. 따라서 이 사원들이 모두 커피를 마시는데 필요한 시간은 100분 정도를 넘지 않는다는 것을 알 수 있습니다. 다시 말하면, 각 사원이 커피를 마시기 위해서는 "평균적으로" 1분 정도의 시간이 필요하다고 결론을 내릴 수 있는 것이죠.
어째서 이런 차이가 발생한 것일까요? 바로 커피를 갖고 가는 시간이 상황에 따라서 달라졌기 때문입니다. 남은 커피가 없을 때는 어쩔 수 없이 긴 시간을 들여 커피를 만들어야 하지만, 한번 커피를 만들어 놓으면 한동안은 커피를 다시 만들 필요가 없습니다. 그 상태에서 누군가 커피를 마시러 왔다면 짧은 시간 안에 커피를 갖고 갈 수 있죠. 따라서 평균적으로는 최악의 경우보다 훨씬 빠른 시간에 커피를 갖고 갈 수 있었던 것입니다.
분할 상환 분석(Amortized Analysis)
어떤 자료 구조의 특정 연산들(operations)의 수행 시간이 상황이나 상태에 따라 달라지는 경우를 우리는 꽤 자주 접할 수 있습니다. 흥미롭게도, 이러한 연산들은 최악의 경우에는 매우 긴 시간을 필요로 하지만 그러한 상황이 자주 발생하지 않는, 위 예시와 비슷한 특징을 갖기도 합니다. 따라서 우리가 이러한 연산들을 어떤 순서로든 \(n\) 번 수행했다고 했을 때, 이를 모두 완료하는데 필요한 시간을 이 연산들이 보이는 최악의 수행 시간에 \(n\)을 곱한 것으로 생각하는 것은 이 연산들의 실제 능력을 과하게 평가절하하는 행동입니다.
대신 \(n\) 번의 연산 시퀀스(sequence)를 모두 처리하는데 필요한 시간의 상한(upper-bound) \(T(n)\)을 어떤 방식으로든지 구할 수 있다면, 우리는 이 연산들이 평균적으로 \( T(n)/n \)의 시간에는 동작한다고 말할 수 있습니다. 이때 \( T(n)/n \)의 값이 최악의 경우에 필요한 수행 시간에 비해 현저히 작다면, 이 연산들이 실제로는 더 좋은 성능을 나타낸다고 결론 지을 수 있겠죠.
이렇게 어느 자료 구조의 연산들의 임의의 시퀀스가 주어졌을 때, 그 시퀀스 위의 모든 연산들이 수행되는 동안 각 연산의 평균적인 수행 시간을 분석하는 방법을 분할 상환 분석(amortized anlaysis)이라고 합니다. 여기서 '분할 상환'이라는 이름이 붙은 이유는 연산의 시퀀스를 수행할 때 길게 걸릴 때의 수행 시간을 잘 쪼갠 후(분할) 짧게 걸릴 때에다 재분배를 해준다(상환)는 식으로 생각하면 편합니다. 그러면 짧게 걸릴 때의 시간은 소폭 증가할 테지만 길게 걸릴 때의 수행 시간을 대폭 낮출 수 있으며, 따라서 평균적으로는 최악의 경우만큼 수행 시간을 필요로 하지 않음을 보일 수 있죠.
분할 상환 분석과 대조되는 분석 방법은 각 연산이 실제로 최악의 경우 걸리는 시간을 분석하는 것으로 이 방법을 최악의 경우 분석(worst-case analysis)이라고 부릅니다. 예를 들어, 위 커피 예제에서 각 사원이 커피를 마시는 데 필요한 시간은 최악의 경우 분석으로는 약 10분이나, 분할 상환 분석으로는 약 1분이 됩니다.
분할 상환 분석과 평균의 경우 분석(average-case analysis)을 헛갈려 하시는 분들이 많이 있습니다. 결론을 말씀드리면, 두 분석은 완전히 다릅니다. 분할 상환 분석은 확률의 개념이 포함되지 않습니다. 대신 임의의 연산의 시퀀스가 주어졌을 때 이를 모두 수행하는 동안 각 연산의 평균 수행 시간을 계산합니다. 가끔 연산 시퀀스의 길이가 충분히 긴 경우(즉, \(n\)이 충분히 큰 경우)를 가정하기도 하지만, 어쨌거나 이는 확률의 영역이 아닙니다.
그에 반해 평균의 경우 분석을 하기 위해서는 입력을 결정하는 특정 확률 분포(probability distribution)가 필요합니다. 이때 분석하는 것은 해당 분포에 따라서 입력이 주어질 때, 알고리즘이 모두 수행되는데 필요한 시간의 평균값입니다. 이는 알고리즘의 확률적 분석(probabilistic analysis of algorithms)의 영역에 속합니다. 관련하여 더 자세한 내용이 궁금하시면 아래 글을 참조하세요.
랜덤 알고리즘과 알고리즘의 확률적 분석 (Randomized Algorithms & Probabilistic Analysis of Algorithms)
요새 알고리즘에 어떻게 확률론이 사용되는지를 공부하고 있습니다. 그러면서 예전에는 잘 몰랐거나 어렴풋이만 알던 내용들을 정확히 바로 잡고 있는데요. 그중에서도 가장 기본적인 내용을
gazelle-and-cs.tistory.com
분할 상환 분석 방법
이번 절에서는 분할 상환 분석을 하는 방법에 대해서 알아 보겠습니다. 어떤 자료 구조의 연산들이 주어졌을 때, 길이가 \(n\)인 임의의 시퀀스를 하나 생각해 보겠습니다. 시퀀스에서 \(i\) 번째 연산을 수행할 때 실제로 필요한 시간을 \(c_i\)라고 하겠습니다. 앞에서 설명한 대로 이를 분할 상환 분석하고 싶다면,
\[ T(n) \geq \sum_{i = 1}^n c_i \]
을 만족하는 전체 수행 시간의 적절한 상한 \(T(n)\)을 찾아야 합니다. 그러면 \( T(n)/n \)이 "최악의 경우에도 평균적인" 연산의 수행 시간이 되겠죠. 이렇게 분석하는 방식을 합계 분석(aggregate analysis)이라고 부릅니다. 참고로 이 방식은 모든 연산들의 수행 시간이 동일하게 분석됩니다.
문제는 연산이 복잡한 경우에는 임의의 연산 시퀀스가 분석하기 까다롭게 수행될 수 있고, 따라서 적절한 \(T(n)\)을 구하는 것이 쉽지 않을 수 있다는 것입니다. 이를 해결하고자 아래에서는 크게 두 가지 방법을 소개합니다.
- 회계법(accounting method): 분석하고자 하는 연산들의 실제 수행 시간 대신 가상의 수행 시간을 설정하고 이를 분할 상환적 수행 시간(amortized running time)으로 치는 방법입니다. 이때, 시퀀스 전체의 실제 수행 시간보다 가상 수행 시간이 반드시 더 길어야 합니다. 다시 말해, \(i\) 번째 연산을 수행할 때 설정된 가상의 수행 시간이 \(\hat{c}_i\)라고 한다면, \[ \sum_{i = 1}^n \hat{c}_i \geq \sum_{i = 1}^n c_i \]를 반드시 만족해야 합니다.
- 퍼텐셜법(potential method): 자료 구조의 모습에 어떤 퍼텐셜 함수(potential function)를 정의한 다음, 매번 연산을 수행할 때마다 실제 수행 시간에 자료 구조의 변화에 따른 퍼텐셜 함수의 변화량을 분할 상환적 수행 시간으로 치는 방법입니다. 예컨대, 퍼텐셜 함수를 \(\Phi\)로 정의했을 때, \(i\) 번째 연산을 수행할 때 어떤 자료 구조의 모습이 \(D_{i - 1}\)에서 \(D_i\)로 바뀌면, \[ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i - 1}) \]로 정의하는 것이죠. 그러면, \[ \sum_{i = 1}^n \hat{c}_i = \sum_{i = 1}^n \left[ c_i + \Phi(D_i) - \Phi(D_{i - 1}) \right] = \sum_{i = 1}^n c_i + \Phi(D_n) - \Phi(D_0) \]가 됩니다. 따라서 \( \Phi(D_n) \geq \Phi(D_0) \)가 되는 것만 보이면 분할 상환 분석이 완성됩니다. 많은 경우, \( \Phi \)는 음이 아닌 값을 가지면서 \( \Phi(D_0) = 0 \)이 되도록 설정되므로 자연스럽게 해당 부분이 성립하게 됩니다.
예제 소개
간단한 예제를 통해서 회계법과 퍼텐셜법이 어떤 식으로 적용되는지 배워 보도록 하겠습니다.
여러분이 자판기를 하나 관리하고 있다고 합시다. 문제를 간략하게 만들기 위해서 자판기에는 한 종류의 캔 음료를 판매하고 있다고 가정합시다. 자판기에는 최대 \(\ell\) 개의 음료 캔이 들어갈 수 있습니다. 자판기는 다음의 두 가지 연산을 처리할 수 있습니다.
- \(\mathsf{get}\): 자판기의 음료를 하나 뽑는다.
- \(\mathsf{recharge}\): 자판기에 음료를 가득 채운다.
음료 하나를 뽑거나 채우는데 1의 시간이 걸린다고 합시다. 처음에는 자판기에 음료가 가득 차 있다고 했을 때 과연 두 연산의 수행 시간은 어떻게 분석될 수 있을까요?
\(\mathsf{get}\)은 하나의 음료만 반환하므로 최악의 경우에도 상수 1의 시간이면 충분합니다. 문제는 \( \mathsf{recharge} \)입니다. 언젠가 자판기에 \(s\) 칸만큼의 공간이 남아 있다면, 총 \(s\)의 시간이 걸리게 됩니다. 이는 최대 \(\ell\)까지 커질 수 있으므로, 최악의 경우 \( \mathsf{recharge}\)의 수행 시간은 \(\ell\)이 됩니다.
하지만 \( \mathsf{recharge} \)는 \( \mathsf{get} \)이 얼마큼 호출되었느냐에 따라 그 수행 시간이 달라지게 될 것입니다. 따라서 분할 상환 분석을 적용한다면 수행 시간이 향상될 것으로 기대할 수 있습니다.
회계법으로 분석하기
먼저 위 자판기 예제를 회계법을 사용하여 분석해 보겠습니다. 이 방법을 사용하기 위해서는 각 연산의 실제 수행 시간 대신 가상의 수행 시간을 제시해야 합니다. 그다음 임의의 연산 시퀀스에 대해서 총 실제 수행 시간보다 총 가상 수행 시간이 항상 크다는 것을 보여야 하지요. 먼저 각 연산의 수행 시간 \(c[\cdot]\)는 다음과 같았습니다.
\[ c[\mathsf{get}] = 1 \quad c[\mathsf{recharge}] = s \]
여기서 \(s\)는 자판기에 남은 칸의 수입니다. 이제 가상의 수행 시간 \(\hat{c}[\cdot]\)을 다음과 같이 두도록 하겠습니다.
\[ \hat{c}[\mathsf{get}] = 2 \quad \hat{c}[\mathsf{recharge}] = 0 \]
그러면 우리는 다음의 정리를 보일 수 있습니다.
정리 1. 회계법을 이용한 분석
길이가 \(n\)인 임의의 연산 시퀀스가 주어졌을 때, \(c_i\)와 \(\hat{c}_i\)를 각각 \(i\) 번째 연산의 실제 수행 시간과 가상 수행 시간이라고 하자. 그러면 항상 \[ \sum_{i = 1}^n \hat{c}_i \geq \sum_{i = 1}^n c_i \]를 만족한다.
[증명] 주어지는 연산 시퀀스를 \(\mathsf{recharge}\)가 불리는 다음마다 매번 끊어 주도록 하겠습니다. 예를 들어, 입력된 연산 시퀀스가
\[ \mathsf{get}, \mathsf{get}, \mathsf{recharge}, \mathsf{get}, \mathsf{recharge}, \mathsf{recharge}, \mathsf{get} \]
와 같다면, 우리는 이를
\[ \left\{ \mathsf{get}, \mathsf{get}, \mathsf{recharge} \right\}, \left\{ \mathsf{get}, \mathsf{recharge} \right\}, \left\{ \mathsf{recharge} \right\}, \left\{ \mathsf{get} \right\} \]
과 같이 나누어 주는 것이죠. 그러면 각각의 묶음은 처음에 \( \mathsf{get} \)이 몇 번 호출되다가 마지막에 \( \mathsf{recharge} \)가 불리는 형태를 보일 것입니다. 이때 처음에 \(\mathsf{get}\)이 한 번도 불리지 않을 수도 있고, 마지막에 \( \mathsf{recharge} \)가 나타나지 않을 수도 있습니다. 각각 위 예제에서 세 번째와 네 번째 묶음에 해당하죠.
이제 이렇게 얻은 묶음은 모두
\[ \sum_{j = 1}^m \hat{c}_j \geq \sum_{j = 1}^m c_j \]
를 만족한다는 것을 보일 것입니다. 여기서 \(m\)은 묶음에 속한 연산의 개수를 뜻하며, 표현의 편의를 위해서 \( c_j \)와 \(\hat{c}_j\)를 해당 묶음의 \(j\) 번째 연산의 실제 수행 시간과 가상 수행 시간이라고 하겠습니다.
먼저 묶음의 마지막에 \( \mathsf{recharge} \)가 호출된 경우를 생각해 봅시다. 우리는 매 \( \mathsf{recharge} \)를 기준으로 묶음을 만들어 주었으므로, 해당 묶음 이전에는 \( \mathsf{get} \)이 호출되지 않았음을 알 수 있습니다. 그러면 현재 묶음의 \( \mathsf{get} \)의 개수만큼 캔 음료를 뽑았을 것이며 따라서 \( \mathsf{recharge} \)가 호출된 때 캔 음료를 자판기에 \( \min(m - 1, \ell) \) 개를 넣게 됩니다. 따라서, 우리는
\[ \sum_{j = 1}^m c_j = m - 1 + \min ( m - 1, \ell ) \leq 2 (m - 1) = \sum_{j = 1}^m \hat{c}_j \]
를 이끌어 낼 수 있습니다.
반대로 묶음의 마지막에 \( \mathsf{recharge} \)가 호출되지 않은 경우에는, 모두 \( \mathsf{get} \)으로만 이루어져 있다는 의미이므로,
\[ \sum_{ j = 1}^m c_j = m \leq 2m = \sum_{j = 1}^m \hat{c}_j \]
가 성립합니다.
원래의 연산 시퀀스는 결국 처음에 만든 묶음을 일렬로 붙여 놓은 것이고, 각 묶음에서 정리의 식이 성립함을 보였으므로 정리의 명제가 참이라는 것을 증명할 수 있습니다. ■
정리 1이 의미하는 바는 각 연산의 수행 시간을 실제 수행 시간 \( c \)가 아니라 가상의 수행 시간 \( \hat{c} \)으로 치환하여 생각해도 임의의 연산 시퀀스에 대해서 항상 적절한 상한을 이룬다는 것입니다. 따라서 \( \hat{c} \)은 적절한 분할 상환적 수행 시간(amortized running time)으로 동작합니다. 이를 통해 우리는 비록 \( \mathsf{get} \)은 원래 수행 시간보다 더 긴 시간으로 책정되었지만 여전히 상수 시간에 동작하며, \( \mathsf{recharge} \)는 최악의 경우 \( O(\ell) \)의 시간에 동작할 것이 분할 상환적으로는 상수 시간에 동작한다고 결론을 지을 수 있습니다.
퍼텐셜법으로 분석하기
같은 예제를 이번에는 퍼텐셜법으로 분석해 보도록 하겠습니다. 이를 이용하기 위해서는 먼저 자료 구조의 모습을 어떤 실수에 대응시키는 퍼텐셜 함수 \( \Phi \)를 정의하여야 합니다. 이 예제에서는 \( \Phi \)를 자판기에 남은 공간의 개수로 정하면 충분합니다. 먼저 자판기에 남은 공간이 음수가 될 수는 없으므로 퍼텐셜 함수는 항상 음이 아닌 수를 가질 것입니다. 게다가 자판기에 처음에는 음료가 가득 들어 있다고 하였으므로 처음 퍼텐셜 함수의 값은 0이 됩니다.
다시 말해, 길이가 \(n\)인 어떤 연산 시퀀스가 주어졌을 때, \(i\) 번째 연산이 처리된 후의 자료 구조의 모습을 \(D_i\)라고 하고 \(D_0\)은 초기 자료 구조의 모습이라고 하면,
\[ \Phi(D_i) \geq 0 = \Phi(D_0) \]
이 항상 성립합니다. 이를 토대로 우리는 \(i\) 번째 연산의 분할 상환적 수행 시간 \( \hat{c}_i \)를
\[ \hat{c}_i := c_i + \Phi(D_i) - \Phi(D_{i - 1}) \]
로 정의할 수 있습니다. 그 이유는, 이를 모든 \(i = 1, \cdots, n\)에 대해 더하였을 때,
\[ \sum_{i = 1}^n \hat{c}_i = \sum_{i = 1}^n \left[ c_i + \Phi(D_i) - \Phi(D_{i - 1} \right]= \sum_{i = 1}^n c_i + \Phi(D_n) - \Phi(D_0) \geq \sum_{i = 1}^n c_i \]
임을 이끌어낼 수 있기 때문이죠.
만약 \(i\) 번째 연산이 \( \mathsf{get} \)이라고 해 보겠습니다. 이 연산을 통해서 남은 공간이 최대 하나 증가할 수 있습니다. (만약 자판기에 음료가 없는 상태라면 남은 공간은 그대로입니다.) 따라서,
\[ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i - 1}) \leq 2 \]
임을 이끌어낼 수 있습니다.
반대로 이번에는 \(i\) 번째 연산이 \( \mathsf{recharge} \)라고 하죠. 이 연산을 수행하기 전에 자판기에 \(s\) 칸의 공간이 남아 있었다고 합시다. 연산이 수행된 후에는 빈 공간이 없어지죠. 따라서
\[ \Phi(D_{i-1}) = s \quad \Phi(D_i) = 0 \]
임을 알 수 있습니다. 실제로 연산이 수행되는 시간은 \( c_i = s \)였으므로, 이를 조합하면
\[ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i - 1}) = s + 0 - s = 0 \]
이라는 것을 유도할 수 있습니다.
이를 통해, 퍼텐셜법을 활용해서도 우리는 두 연산이 모두 분할 상환적으로 상수의 시간에 동작한다고 결론을 내릴 수 있습니다.
마치며
이번 시간에는 분할 상환 분석이 무엇이고, 이것이 왜 중요하며, 어떤 식으로 적용할 수 있는지를 알아보았습니다. 한 마디로 정리하자면, 분할 상환 분석은 상황에 따라 성능이 크게 변동하는 연산이나 알고리즘의 "최악의 경우에도 평균적인" 성능을 측정하여 해당 연산이나 알고리즘의 실제 성능을 과도하게 평가절하하는 것을 막을 수 있는 분석 기법입니다.
이미 많은 알고리즘들이 분할 상환 분석을 통해서 최악의 경우보다 실제로는 더 좋은 성능을 보인다고 분석이 되었습니다. 좀더 정확히 말하자면 최악의 경우의 상황이 그리 많이 일어나지 않고 따라서 최악의 경우의 성능을 다른 좋은 성능을 보인 때에 분배할 수 있음을 보인 것이죠. 기회가 되면 분할 상환 분석을 사용하는 다른 자료 구조나 알고리즘을 소개하는 시간을 갖도록 하겠습니다. 특히 현재 제가 다음에 포스팅하려고 호시탐탐 노리고 있는 주제는 서로소 집합(disjoint set) 자료 구조입니다. 잘 준비해서 정리할 수 있도록 하겠습니다.
글의 내용에 잘못이 있거나, 궁금하신 점이 있으시면 알려 주세요. 고맙습니다. :)
참조
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition. MIT Press 2009.
'알고리즘 기초 > Algorithm design' 카테고리의 다른 글
| 탐욕 알고리즘 분석하기 (Correctness of Greedy Algorithms) (22) | 2020.08.08 |
|---|
