728x90
1초 제한
n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다.
예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면
1. O(N) 의 시간복잡도일 경우에 값이 10만 정도이니, 1/1000초 정도가 걸릴 것이라고 예상할 수 있다.
2. O(N^2)의 시간복잡도의 경우에 값은 100억이므로, 100초 정도가 걸릴 것이라고 예상할 수 있다.
보통 1초가 걸릴 때 입력의 최대 크기를 살펴보면
- O(N): 약 1억
- O(N^2) : 약 1만
- O(N^3) : 약 500
- O(2^N) : 약 20
- O(N!): 10
N의 크기에 따른 허용 시간 복잡도
| N의 크기 | 시간복잡도 |
| N ≤ 11 | O(N!) |
| N ≤ 25 | O(2N) |
| N ≤ 100 | O(N4) |
| N ≤ 500 | O(N3) |
| N ≤ 3,000 | O(N2logN) |
| N ≤ 5,000 | O(N2) |
| N ≤ 1,000,000 | O(NlogN) |
| N ≤ 10,000,000 | O(N) |
| N > 10,000,000 | O(logN), O(1) |
복잡도 소요 시간 예시
- O(1)
- 스택 Push, Pop
- O(log n)
- 이진 트리
- O(n log n)
- 퀵 정렬
- 병합 정렬
- 힙 정렬
- O(n)
- for문 (하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우)
- 컬렉션의 절반 이상을 반복하는 경우
- O(n^2)
- 이중 for문 (두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우)
- 삽입 정렬
- 버블 정렬
- 선택 정렬
- O(C^n)
- 피보나치 수열
728x90