C++ 시간 복잡도 계산

  Big-O 수행 시간

(빠름) O($1$) < O(log$_{2}n$) < O($n$) < O($n$log$n$) < O($n^2$) < O($n^3$) < O($2^n$) (느림)

 

C++에서는 1초에 약 1억 번 정도의 연산을 수행할 수 있다.

시간 제한이 2초면 연산 횟수는 2억 번 이내여야 하는 것이다.

 

원소 백만 개($10^6$)까지는 O($n$log$n$)으로 커버 가능하다. => stl의 sort 사용 가능

원소 천만 개($10^7$)까지는 O($n$)으로 커버 가능하다.

 

  stl 컨테이너

set, map과 같은 associative container의 경우 red-black tree 기반으로 노드 검색/삽입/삭제 O(log$n$)이다.

자동으로 정렬되지 않는 unordered_set, unordered_map은 해시 기반으로 노드 검색/삽입/삭제 O(1)이다.