시간 제한과 시간 복잡도
- 코딩 테스트에서 문제의 제한 시간은 보통 1~5초 정도이다.
- 일반적인 CPU 기반의 PC나 채점용 컴퓨터에서 1초에 실행할 수 있는 최대 연산 횟수는 약 1억번이다.
- 따라서 문제를 풀 때 먼저 시간 복잡도를 확인하여 어떤 알고리즘을 써서 코딩을 해야할지 가늠을 할 수 있다.
ex) 문제에서 주어진 N의 최대값이 10만이며, 주어진 제한 시간은 1초라면?
시간 복잡도가
O(N^2)인 알고리즘의 연산 횟수는 10만번*10만번 = 100억번이므로 사용할 수 없다.
1초에 최대 연산 횟수(최대 입력 크기)
| 시간 복잡도 | 최대 연산 횟수 |
|---|---|
| O(N) | 약 1억번 |
| O(N^2) | 약 1만번 |
| O(N^3) | 약 500번 |
| O(2^N) | 약 20번 |
| O(N!) | 10번 |
제한 시간이 1초 일 경우, N의 범위에 따른 시간 복잡도 선택
- N의 범위가 500: 시간 복잡도가
O(N^3)이하인 알고리즘을 설계 - N의 범위가 2,000: 시간 복잡도가
O(N^2)이하인 알고리즘을 설계 - N의 범위가 100,000: 시간 복잡도가
O(NlogN)이하인 알고리즘을 설계 - N의 범위가 10,000,000: 시간 복잡도가
O(N)이하인 알고리즘을 설계 - N의 범위가 10,000,000,000: 시간 복잡도가
O(logN)이하인 알고리즘을 설계
Reference.
- 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈 저
