시간·공간 복잡도 (Big-O) 제대로 읽기

왜 배우는가

같은 정답이어도 느린 코드는 큰 입력에서 시간 초과가 납니다.
Big-O는 “상수 몇 배”가 아니라 n이 커질 때 지배적인 성장을 말합니다.

흔한 계급 (대략 빠른 순)

표기	이름	감각 (n=10³)
O(1)	상수	맵/배열 인덱스 접근
O(log n)	로그	이분 탐색
O(n)	선형	한 번 훑기
O(n log n)	선형로그	비교 정렬
O(n²)	제곱	이중 루프
O(2ⁿ) / O(n!)	지수·팩토리얼	부분집합·순열 전부

코딩 테스트 감각: n≤10⁵이면 보통 O(n log n)까지, n≤10³이면 O(n²)도 종종 통과.

어떻게 세는가

가장 안쪽 작업이 몇 번 도는가
루프가 겹치면 곱, 이어지면 합 (지배항만 남김)
상수·낮은 차수는 보통 무시 (3n + 100 → O(n))

// O(n)
for (let i = 0; i < n; i++) sum += a[i];

// O(n²)
for (let i = 0; i < n; i++)
  for (let j = 0; j < n; j++) ...

// O(n log n)  ·  정렬
a.sort((x, y) => x - y);

공간 복잡도

추가로 쓰는 메모리입니다. 입력 배열 자체는 보통 제외하거나 문제에 따라 따로 말합니다.

투포인터 회문: 추가 O(1)
해시로 빈도: 추가 O(k) (서로 다른 키 수)

함정

“중첩 루프 = 무조건 n²”은 아닙니다. 안쪽 루프가 n이 아니라 26이면 O(n)에 가깝습니다.
매 단계에서 크기가 절반이면 로그입니다 (이분 탐색).
재귀 깊이가 n이면 콜스택 공간 O(n)을 잊지 마세요.

문제 읽기 체크리스트

n의 상한이 어디에 적혀 있는가
내 초안 복잡도가 그 상한에 맞는가
더 빠른 자료구조(해시·정렬·투포인터)로 줄일 수 있는가

연습

이중 루프로 짠 뒤, “한 번만 훑으면 되나?”를 항상 한 번 더 물어보세요.
다음 레슨(투포인터·해시)이 그 답을 줍니다.