tose33

Amortized time complexity는 한국어로 번역한다면 분할 상환 시간복잡도라고 할수 있겠다. 예전부터 자료구조나 알고리즘의 레퍼런스에서 amortized constant time, amortized linear time 등 amortized란 단어가 붙은 시간복잡도를 꽤 봤는데 대충 넘기다가 이번에 제대로 찾아봤다. 내가 이해한 바로는 분할 상환이라는 이름대로, 알고리즘 수행 중 비정상적으로 많은 시간을 소요하는 연산을 분할해서, 나머지 낮은 시간을 소요하는 연산에 분배(상환)해 알고리즘의 시간 복잡도를 판단한다는 것이다. C++ STL의 container중 vector의 push_back 연산을 예로 들어보자. c++의 vector는 내부적으로 다음과 같이 동작한다. 1. vector를 ..