코딩테스트에서 시간 복잡도와 공간 복잡도를 주어질 때가 많다. 최악의 경우에서 알고리즘이 주어진 조건을 만족할 수 있는지 판단할 수 있어야 한다.
시간 복잡도: 얼마만큼의 시간이 소요되는가공간 복잡도: 얼마만큼의 용량이 필요한가
시간복잡도
| 연산 횟수(N) | 허용 시간 복잡도 |
|---|---|
| N<12 | O(N!) |
| N<26 | O(2^N) |
| N<100 | O(N^4) |
| N<500 | O(N^3) |
| N<3000 | O(N^2 * logN) |
| N<5000 | O(N^2) |
| N<1백만 | O(NlogN) |
| N<1천만 | O(N) |
공간 복잡도
1.2억개의 int(4Byte)를 저장하는데 약 512MB 정도의 공간이 쓰임