amortized 복잡도 : average complexity와 뭐가 다른가요?

 링크는 c++의 vector의 push_back에 대해서 설명한 문서입니다. Complexity가 constant라고 되어 있는데요. 괄호가 떡하니 쳐져 있습니다. amortized time이라고요. 이게 왜 나왔는지부터 예를 들어서 이야기 보겠습니다.

 

---

 vector의 초기 size가 무한대이지 않는 이상 (기본적으로 적절한 size) 최악의 경우에는, O(vector의 size) 만큼 나올 겁니다. 만약에 n개가 있으면 O(n)이 나올 겁니다. 더 정확하게 말하면 linear time 입니다. worst case인 경우에는 그게 맞습니다.

 

 

 기존에 n개의 item이 있었습니다. capaity 역시 n이였고요. 만약에 grow rate가 2인 경우에, 이 시점에서 push_back이 호출된 경우에, 2배로 capacity를 뻥튀기 시켜버립니다. 저는 속칭 2배 뻥이라고 이야기 합니다.

 

 

 그러면, push_back은 최악의 경우에 O(n)이 아닌가요? 맞습니다. 이것도 일리가 있는 말입니다. 왜냐하면, 2n개의 원소를 저장할 수 있는 새로운 배열을 생성한 다음에, 기존의 배열은 삭제하기 때문입니다.

 

 

그리고 1개의 item을 추가했다면, 위 그림과 같은 상황이 됩니다. 여기서, 우리는 한 가지 의문을 가질 수 있습니다. n-1개의 item을 그냥 push_back 해도 되지 않은가? 고작 최악의 경우라도 몇 번 일어나지도 않는 expand 연산 때문에, 최악 복잡도가 O(n)이라고 평가하기는 너무 박하지 않나?

 

 

 당연하게도, 1개를 또 뒤에 추가하는 연산을 수행했을 때, expand는 일어나지 않았습니다. 이미 원소가 추가로 들어갈 수 있는 공간은 1개 이상이였기 때문입니다. 그러면 이렇게 생각하면 어떨까요? n개에서 2n개로 확장된 다음에 또, n개가 추가되었습니다. 그러면 연산은 n회 일어난 겁니다.

 

 

 대충 이 상황이 된 후에 push_back이 되는 경우에는 이미 2n개의 item이 찬 상태이기 때문에, 2배로 확장되는 경우에는 4n개의 크기를 가진 배열이 새로 생성됩니다.

 

 

 그리고 2n개의 item은 새 배열에 복사가 되고, 2n개의 기존 배열은 삭제됩니다. 삽입, 삭제, 복사 비용을 각각 1이라고 한다면, 총 8n이 들었습니다. 연산 수는 n회입니다. 8n/n = 8입니다. 비록, expand 연산이 비싸지만, 최악의 경우, 그러니까 push_back 연산이 엄청나게 많이 일어나는 경우에, 이를 총 연산수로 나눈 값이 상수로 떨어진다는 이야기입니다.

 

 그러므로, amortized 복잡도는 constant다. 라고 말해도 되겠네요. 사실 그게 더 합리적일 겁니다.

 

---

 그런데, 이것은 average 복잡도와는 차이가 있습니다. 당연하게도요. 예를 들어서, Linked List로 Chaining을 하는 HashMap을 생각해 보겠습니다. 이 자료구조에 원소를 넣는 평균 복잡도는 Constant로 잘 알려져 있습니다. 당연하게도, 이 글과, 이 문서를 봐도 알 수 있는 내용입니다. 그런데, 해당 문서에서 몇 문구만 잘 읽어보면, unordered_map (hash 계열 자료구조)의 put (1개를 추가하는 연산)의 평균 복잡도가 Constant라고 했지, amortized 복잡도가 Constant 하다고는 하지 않았습니다. 그 대신에, 최악의 경우에는, linear하다고만 언급하고 있습니다.

 

 용례가 다른 거 눈치를 채셨으리라 생각합니다. 왜 amortized Constant라고 하지 않을까요?

 

 

 새로 추가해야 할 키를 k'이라고 해 보겠습니다. 이것의 해시값이 0이였다고 하면, 0번 버킷에 추가는 하긴 할 겁니다. 문제는, 우리가 흔히 알고 있는 unordered_map의 경우, 키값 중복을 허락하지 않는다는 것입니다. 중복을 허락하지 않으려면, 넣을 때, 해당 Key가 있는지 찾아 봐야 합니다.

 

 그럴려면 [0]번 버킷에 있는 키 전체를 다 뒤지는 수밖에 없습니다. 최악의 경우에는, [0]번에 추가되는 상황일 겁니다.

 

 

 다음에 키 값이 k''인 것도 추가될 거에요. 당연하게도, 최악의 경우에는 충돌이 매우 많이 난 0번 버킷에 들어가는 경우일 겁니다.

 

 

 이런 식으로 계속 들어가는 경우에, 최악은 O(n)이 나옵니다. 그러면, average case가 Constant이고 최악이 O(n)이다. 라는 것이 의미가 있는 상황인 셈입니다. average case의 경우에는 확률이 들어갑니다. 예를 들어서, 정렬된 배열에서 어떤 수 x를 추가해야 한다고 해 보겠습니다. 그리고 추가한 뒤에도 정렬된 상태를 유지해야 한다고 해 봅시다.

 

 

 그러면, 이 경우에 평균 복잡도는 어떻게 계산이 될까요?

 

 

 new가 a[n-1]보다 크거나 같아서 뒤에 추가하면 되는 경우에는 비교, 대입만 수행하면 끝날 겁니다. 이를 단위 1이라고 합시다. 그러면 그 상황이 나타날 확률에 1을 곱한 것이 가중치에 더해집니다. 이 사건을 p(n-1)이라고 하겠습니다.

 

 

 그 다음에는 어떨까요? a[n-2]보다는 크거나 같지만, a[n-1]보다 작을 확률. 이를 사건 p(n-2)라고 하겠습니다. 그러면 이 경우에는 맨 마지막 원소인 a[n-1]하고 비교하고, a[n-2]하고 비교하고, a[n-1]을 뒤로 이동시키고, new를 대입해야겠죠. 이걸 편하게 단위 2라고 합시다.

 

 그러면, 이 상황이 나타날 확률 p(n-2)에 2를 곱한 것이 또 가중치에 더해질 겁니다. 중요한 것은, 확률에 의해서 계산된 가중치들이 평균 복잡도를 구하는 데 쓰인다는 것입니다. 더 정확하게 말하면, 모든 Input에 대해서 수행 시간의 평균을 구해서 산출하는 셈입니다. 뭔가 어렵다. 결론은 예제 하나만 이해하시면 됩니다. unordered_map의 put 연산은 amortized Constant라고 하지 않고, average Constant라고 한다.