c++) 함수 별 시간복잡도
각 함수마다 시간복잡도가 다른데, 항상 쓸때마다 레퍼런스에서 대충 찾아보고 지나가서 까먹는다.
앞으로 쓸때마다 여기에 기록해 나갈 예정.
Constant time - O(1)
Linear time - O(n)
Logarithmic time - O(logn)
Linearithmic time - O(nlogn)
Quadratic time - O(n^2)
Cubic time - O(n^3)
(시퀸스 컨테이너, Sequence Container)
- vector
요소들이 메모리상 연속적으로 저장된다.
처음 vector가 생성될때 여유를 갖고 생성되고, 생성된 메모리 초과시 새로 만들어 재할당됨. (값들 복사)
접근: O(1)
검색: O(n)
뒤 삽입, 삭제: amortized O(1)
중간 추가, 삭제: O(n)
벡터에서 삭제가 일어나면, 삭제지점 이후의 모든 원소들이 한칸씩 땡겨지기 때문. 추가도 마찬가지.
- deque
vector와 다르게 메모리상 연속적으로 저장되지 않음 -> 일정 단위의 chunk로 쪼개어져 있고 재할당이 일어날때 chunk 단위로 늘어남.
= 이 말은 즉, 저장할 원소들이 많고 메모리 할당량이 큰 경우 vector 비용이 저렴하다.
vector보다 확장이 용이하다.
접근: O(1)
검색: O(n)
앞,뒤 추가, 삭제: amortized O(1)
중간 추가, 삭제: O(n)
(연관 컨테이너, Associative Container)
- set
연관컨테이너, 검색이 빠르다.
접근: 불가
검색: O(logn)
삽입, 삭제: O(logn)
- map
접근: 불가
검색 (find 함수) : O(logn)
삽입, 삭제: O(logn)
(컨테이너 어댑터, Container Adapter)
- stack
디폴트 원형이 deque
접근: 불가
검색: 불가
삽입, 삭제: amortized O(1)
원형이 deque이고, 맨 뒤의 삽입, 삭제만 가능하기 때문에 O(1)
- queue
접근: 불가
검색: 불가
삽입, 삭제: amortized O(1)
- priority_queue
접근: 불가
검색: 불가
삽입, 삭제: O(logn)
sort: 평균적으로 O(nlogn)
reverse: O(n) in half the distance between first and last
next_permutation: 최악 O(n)
max_element: O(N)
iterator를 이용해 모든 요소를 비교하기 때문에 O(N)이다.
sort는 컨테이너를 이용한 비교이기 때문에 더 적은 시간인 O(nlogn)의 시간이 걸릴수있지만, max_element는 iterator를 이용한 비교이기 때문에 더 긴시간인 O(N)이 걸린다.