시간 제한과 시간 복잡도
- 코딩 테스트에서 문제의 제한 시간은 보통 1~5초 정도이다.
- 일반적인 CPU 기반의 PC나 채점용 컴퓨터에서 1초에 실행할 수 있는 최대 연산 횟수는 약 1억번이다.
- 따라서 문제를 풀 때 먼저 시간 복잡도를 확인하여 어떤 알고리즘을 써서 코딩을 해야할지 가늠을 할 수 있다.
제한 시간이 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)이하인 알고리즘을 설계
