배열 길이, 정점 수, 간선 수처럼 커지는 축을 먼저 정한다.
complexity audit
시간·공간복잡도는 같은 표에서 분리해 판정한다
반복 범위, 입력 크기, 숨은 비용을 먼저 고정한 뒤 시간과 추가 공간을 따로 적는다.
가능
주의
판정 순서
평균이 아니라 최악 입력에서 반복·재귀가 얼마나 커지는지 본다.
정렬, 해시, 복사, 큐/스택 같은 보조 비용을 시간·공간에 따로 넣는다.
| 패턴 | N ≤ 1,000 | N ≤ 100,000 | N ≥ 1,000,000 | 추가 공간 |
|---|---|---|---|---|
| O(1) | 통과 | 통과 | 통과 | 카운터 수준 |
| O(N) | 통과 | 통과 | 대체로 통과 | 배열·해시 O(N) 여부 확인 |
| O(N log N) | 통과 | 통과 | 상수와 메모리 확인 | 정렬 버퍼, 재귀 스택 |
| O(N²) | 작으면 가능 | 위험 | 부적합 | 2D DP면 O(N²) 공간도 함께 위험 |