C++ STL 컨테이너, string 클래스 함수 시간복잡도

https://www.acmicpc.net/problem/5430

5430번: AC

이 문제에서 vector 의 erase와 string erase, find 함수를 사용했는데, 계속해서 시간초과가 났다.
vector erase함수를 O(1)로 생각해서 그렇게 썼는데, 실은 O(N)의 시간복잡도를 가지고 있었다..무지ㅋㅋ
그런 참에 시간복잡도를 정리해보려고 한다

Vector<T>
[],at를 통한 접근 - O(1)
find() - O(N)
insert(), erase() - O(N)
pop_back() - amortized O(1) 
push_back() - amortized O(1)

Deque<T>
[],at를 통한 접근 - O(1)
find() - O(N)
insert(), erase() - O(N)
pop_front() - O(1)
push_front() - O(1) 
pop_back() - O(1)
push_back() - O(1)

 

string
+= : O(N)
+ : O(N^2)
insert(),erase() - O(N)
find() - O(N) 

*amortized O(1)
보통 O(1)인데 capacity가 꽉차면 기존 메모리를 해제하고 새로운 메모리를 할당하여 옮기게 된다.
이 때 O(N)의 복잡도를 갖게된다. 즉 드물게 O(N)이 될수도 있다는 것이다.

*참고한 사이트
https://80000coding.oopy.io/cf49e471-7acb-4130-8654-fcfeed13bda5

[C++] vector STL method 시간복잡도

https://blog.naver.com/yoochansong/221739086178

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

https://sunho-doing.tistory.com/entry/CC-C-STL-deque

[C++] STL - deque