Amortized time complexity

Amortized time complexity는 한국어로 번역한다면 분할 상환 시간복잡도라고 할수 있겠다.

 

예전부터 자료구조나 알고리즘의 레퍼런스에서 amortized constant time, amortized linear time 등 amortized란 단어가 붙은 시간복잡도를 꽤 봤는데 대충 넘기다가 이번에 제대로 찾아봤다.

 

내가 이해한 바로는 분할 상환이라는 이름대로, 알고리즘 수행 중 비정상적으로 많은 시간을 소요하는 연산을 분할해서, 나머지 낮은 시간을 소요하는 연산에 분배(상환)해 알고리즘의 시간 복잡도를 판단한다는 것이다. 

 

 

C++ STL의 container중 vector의 push_back 연산을 예로 들어보자.

c++의 vector는 내부적으로 다음과 같이 동작한다.

 

1. vector를 만들면 내부적으로 임의의 크기의 메모리가 vector에게 자동적으로 할당된다. 

 

2. push_back 연산으로 데이터를 벡터에 추가하다가 할당 받은 메모리가 꽉 찬다면 더 큰 메모리를 다른 곳에 할당하고 지금까지 벡터에 저장되어 있던 데이터를 그대로 옮기는 memory allocation이 일어난다. 이때 O(N)의 시간이 걸린다. 

 

즉 벡터의 push_back 연산은 거의 항상 constant 시간이 걸리지만, 할당 받은 메모리가 꽉 찼을때만 linear 시간이 걸린다. 따라서 만약 그냥 빅오 노테이션으로 최악의 시간을 계산한다면 push_back 연산은 O(N)을 갖게 될 것이다.

 

하지만 이는 push_back 연산에게 너무 가혹한 처사라고 할 수 있다... 

정작 O(N)의 시간이 걸리는 경우는 가끔가다 한번인데 (심지어 애초에 벡터의 크기를 내가 사용할 만큼 정해놨다면 그런 경우를 아예 방지할수 있다) 해당 연산의 시간복잡도를 O(N)으로 정해버리는건 해당 연산을 제대로 평가하지 못했다고 볼수 있다. 

 

이럴때 필요한것이 amortized time complexty, 분할 상환 시간복잡도로 분석하는 것이다. 

비정상적으로 많은 시간이 걸리는 memory reallocation의 시간을 분할해서 나머지 평상시의 벡터의 끝에 데이터를 푸쉬하는 연산에 분배하는 것이다. 

 

cpp reference의 push_back 연산의 complexity를 보면 다음과 같이 나타나 있는 것을 볼 수 있다. 

Complexity는 Constant (O(1)), amortized time.

reallocation이 일어날수 있다. 만약 reallocation이 발생한다면 벡터의 크기 즉 O(N)이 소요됨.

 

https://www.cplusplus.com/reference/vector/vector/push_back/

vector::push_back - C++ Reference