시간복잡도 예측

백준 채점 환경

• 클럭 2.9GHz = 29억Hz = 29억/초
• 코어 10개 = 290억/초 이긴 한데, 서버가 한 문제에 1코어만 쓰지 않을까
• += 는 어셈블리어 연산 3번

시간복잡도

대략 1초에 1억번 한다고 생각

N > 100,000,000 : O(logN), O(1)
N <= 100,000,000 : O(N)
N <= 1,000,000 : O(NlogN)
N <= 10,000 : O(N^2)
N <= 3,000 : O(N^2logN)
N <= 500 : O(N^3)
N <= 100 : O(N^4)
N <= 25 : O(2^N)
N <= 11 : O(N!)

시간복잡도 별 유형

• 입력이 100 이하인 경우
  o 완전 탐색 (dfs, bfs)
  o 백트래킹
• 입력이 10,000 이하인 경우
  o 최대 O(n^2) 이내로 끝내야하는 문제
  o 문제에 따라 O(n^2 log n)까지는 허용
  o n*n 2 차원 리스트를 모두 순회해야하는 문제가 많음
• 입력이 1,000,000 이하인 경우
  o 최대 O(n log n)으로 끝내야하는 문제
  o 힙, 우선순위 큐
  o 정렬
  o 동적 계획법
  o 위상 정렬
  o 다익스트라 알고리즘
• 입력이 100,000,000 이하인 경우
  o 최대 O(n)으로 끝내야하는 문제
  o 동적 계획법
  o 그리디
• 그 이상인 경우
  o 최대 O(log n)으로 끝내야하는 문제가 많음
  o 거의 안나오는 문제 유형
  o 이진탐색