Big-O 표기법 — 실무 개발자를 위한 최소한

핵심 요약

Big-O는 "입력이 커질 때 실행 시간이 어떻게 늘어나는가"를 나타낸다. 정확한 초 단위가 아니라 증가율이다. 실무에선 딱 몇 가지만 구분할 줄 알면 된다 — 특히 중첩 반복(O(n²))과 반복 안의 DB 조회(N+1)를 알아채는 것이 핵심이다.

1. 자주 나오는 복잡도

2. 코드로 보기

// O(n) — 한 번 순회
for (const x of arr) sum += x

// O(n²) — 중첩 → 데이터 커지면 폭발
for (const a of arr)
  for (const b of arr)
    if (a + b === target) ...

// O(1) — 해시맵으로 O(n²)를 O(n)으로
const seen = new Set()
for (const x of arr) {
  if (seen.has(target - x)) return true
  seen.add(x)
}

3. 실무에서 진짜 중요한 것

• 중첩 반복 경계 — for 안의 for, 또는 arr.includes()를 반복 안에서(사실상 O(n²))
• 반복 안의 I/O — 루프마다 DB 쿼리·API 호출(N+1). Big-O보다 상수(네트워크 지연)가 훨씬 크다
• 자료구조 선택 — "포함 여부" 체크는 배열(O(n)) 대신 Set/Map(O(1))

4. 함정

• Big-O는 상수를 무시한다. n이 작으면 O(n²)가 O(n log n)보다 빠를 수도 있다 — 무작정 이론만 보지 말 것
• 공간 복잡도(메모리)도 같은 방식으로 본다 — 캐시를 위해 O(n) 메모리를 쓰는 트레이드오프

자주 묻는 질문

실무에서 Big-O를 꼭 알아야 하나요?

정밀한 증명은 필요 없지만, "이 반복이 데이터 커지면 몇 배로 느려지나"를 직관적으로 아는 건 필수입니다. 대부분의 성능 사고는 O(n²) 로직이나 반복 안의 쿼리에서 나옵니다.

O(log n)은 왜 빠른가요?

매 단계에서 후보를 절반으로 줄이기 때문입니다(이진 탐색). 데이터가 100만 개여도 약 20번이면 찾습니다. DB 인덱스(B-Tree)가 빠른 이유도 이것입니다.

O(n²)를 어떻게 개선하나요?

흔한 방법은 해시맵/Set으로 "찾기"를 O(1)로 바꾸거나(중복·짝 찾기), 미리 정렬(O(n log n)) 후 투 포인터를 쓰는 것입니다. 반복 안의 DB 조회는 한 번의 IN 쿼리나 조인으로 묶으세요.