[참고자료] 라이브러리 함수들의 시간복잡도

#include <algorithm>

sort(begin, end) / sort (begin, end, compFunction) -> 퀵정렬과 힙정렬을 이용

시간 복잡도 : O(N logN)

 

stable_sort(begin, end)

시간 복잡도 : 충분한 메모리가 있다면 O(N logN), 충분한 메모리가 없다면 O(N logN^2)

 

partial_sort(begin, begin+index, end)

: 전체 배열에서 1~index 원소 까지만 정렬

시간 복잡도 : O(N logM) (전체 원소 개수 N, index의 크기 M)

 

binary_search(begin, end, findValue)

시간 복잡도 : O(log N)

 

lower_bound(begin, end, findValue) -> binary_search를 이용

: 처음 findValue 값이 나오는 곳의 위치를 반환

int index = lower_bound(v.begin(), v.end(), 3) - v.begin(); // 길이를 넘는 값을 찾으면 길이를 반환

시간 복잡도 : O(log N)

 

upper_bound(begin, end, findValue)

: 처음 findValue 값이 나오지 않는 곳의 위치를 반환

시간 복잡도 : O(N logN)

 

find(begin, end, findValue)

시간 복잡도 : O(N)

 

reverse(begin, end)

시간 복잡도 : O(N)

 

fill(begin, end, value) -> memset보다 느리지만 안전하다

시간 복잡도 : O(N)

#include <vector>

v.insert / v.erase

시간 복잡도 : O(N)

 

v.push_back / pop_back

시간 복잡도 : O(1)

 

unique(begin, end)시간 복잡도 : O(N)

#include <list>

l.erase / l.insert

시간 복잡도 : O(1)