컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다.
따라서 코딩 테스트의 경우 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각하면 된다.
예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안된다.
제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 N의 가용 범위는 아래와 같다.
| 시간 복잡도 | N의 가용 범위 |
| O(N!) | 10 |
| O(2ⁿ) | 20~25 |
| O(N³) | 200~300 |
| O(N²) | 3,000 ~ 5,000 |
| O(NlogN) | 100만 |
| O(N) | 1,000~2,000만 |
| O(logN) | 10억 |
시간 복잡도 초과 예제)
제약 조건
- 정수 배열의 길이는 2이상 10⁵입니다.
- 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하입니다.
정수 배열의 길이는 최대 10⁵ 즉, 10만이다.
따라서 O(N²)은 사용할수가 없다.
그럴리는 없지만 제한 시간이 34초 이상이라면 3,000 x 34가 10만을 초과하므로 가능할것이다.
