[PS] 시간복잡도 - 코딩테스트 TIP

코딩테스트 문제를 풀 때, 입력의 크기 n에 대해 시간초과가 나지 않도록 알고리즘을 고려해야 한다.

이 사실을 알고 있지만, 항상 특정 시간복잡도에 대해 n의 크기를 어느정도까지 가져갈 수 있는지를 까먹어 해당 글을 작성하게 됐다.

 

1️⃣ 입력의 크기에 따른 시간복잡도

입력의 크기	시간복잡도	대표 알고리즘
n <= 10	\[O(n!)\]	완전탐색
n <= 20	\[O(2^n)O(n^2*2^n)\]	Bitmask DP
n <= 50	\[O(\sqrt{2}^n)\]	MITM
n <= 500	\[O(n^3)\]	Matrix Chain Multiplication(행렬 곱셈)
n <= 5,000	\[O(n^2)\]
n <= 100,000	\[O(n\sqrt{n})O(n\log^{2}n)\]	모스(Mo's) 알고리즘
n <= 1,000,000	\[O(n\log n)\]	정렬, LIS(최장 증가 부분 수열)
n <= 10,000,000	\[O(n)\]	DP, DFS, Tree traversal
그 이상	\[O(\log n),O(1)\]	이분 탐색, 해시

 

 

해당 값에 대한 자세한 설명을 알고 싶다면, 아래 블로그를 참고하도록 하자.

PS, 코테 입문자들을 위한 백준 가이드 (시간복잡도, 언어별 추가 시간, solved.ac)