점검표

코드에서 시간·공간복잡도 판정하기

반복 범위, 자료구조 연산, 보조 메모리를 같은 표에 놓고 보면 Big-O 결론과 입력 규모 판단을 함께 정리할 수 있습니다.

시간·공간복잡도 판정 순서

1

N 기준값

배열 길이, 정점 수, 간선 수처럼 입력 축을 먼저 정합니다.

2

가장 많이 도는 경로 선택

평균이 아니라 최악 입력에서 반복과 재귀가 얼마나 늘어나는지 봅니다.

3

숨은 비용 반영

정렬, 삽입, 해시, 복사, 재귀 스택을 시간과 공간에 따로 더합니다.

입력 규모별 비용 기준표

패턴코드 신호
N ≤ 1,000작은 입력
N ≤ 100,000일반 제한
N ≥ 1,000,000큰 입력
O(N)단일 순회
통과권상수 확인
통과권메모리 확인
우선 후보스트리밍 고려
O(N log N)정렬, 힙
통과권구현 단순
가능상수 리스크
코드에서 시간·공간복잡도 판정하기 한계시간 측정
O(N²)쌍 비교
가능약 백만 번
위험십억 단위
부적합구조 변경

O(1) 공간

카운터와 포인터처럼 입력 크기와 무관한 변수만 추가합니다.

O(N) 공간

보조 배열, 해시맵, 큐처럼 입력에 비례하는 저장소를 만듭니다.

숨은 공간

재귀 프레임, 정렬 버퍼, 슬라이스 복사도 보조 공간에 포함합니다.