입력 크기별 복잡도 예산

입력 크기로 읽는 복잡도 예산표

상수항보다 먼저 N의 최대값과 반복 구조를 맞춰 보면 O(N^2), O(N log N), O(N)의 경계가 빨리 드러납니다.

N 기준

최대 입력을 먼저 읽는다

시간 제한 안에서 가능한 반복 횟수 범위를 잡아야 복잡도 식이 실전 판단으로 이어집니다.

중첩 루프

두 축이 독립인지 확인

겉보기 이중 루프라도 포인터가 되돌아가지 않으면 전체 비용은 선형일 수 있습니다.

보조 공간

테이블 크기를 같이 계산

정렬, 해시, DP 배열은 시간 개선 대신 메모리 예산을 사용한다는 점을 함께 기록합니다.

제출 전 남길 증거

작은 N N이 1,000 안팎이면 O(N^2)도 후보가 될 수 있습니다.
중간 N 100,000 규모에서는 정렬이나 선형 스캔 중심으로 설계를 좁힙니다.
큰 N 수백만 이상이면 불필요한 복사와 추가 테이블 크기까지 같이 줄입니다.