[C++] STL container 시간 복잡도 및 특징 비교

※용어 설명※

amortized : 분할 상환하다는 뜻을 가지고 있는 이 단어는, 쉽게 설명하자면 최악의 경우는 더 높은 값의 시간 복잡도를 가질 수 있지만, 대체적으로는~ 으로 생각하면 될 것 같다.

점근적 분석(Asymptotic analysis)으로 보면 O(n)이 나오는 경우에, 분할상환분석(Amortized Analysis)으로 보면 O(1)이 나오는 경우도 있기 때문이다.

​

red-black tree: 레드블랙트리. Balanced Binary-Search Tree로 이루어진 구조.

 

[출처] C++ STL container 시간 복잡도 및 특징 비교.|작성자 Chan