시간복잡도를 패턴으로 읽기: 코드 모양으로 Big-O를 추정하는 10가지 규칙

이 글의 주제는 알고리즘 교육 계정 @algomasterio의 릴스에서 영감을 받았습니다. 설명·코드·시각화는 모두 이 블로그를 위해 새로 작성하고 구현했습니다. 아래 한 장의 보드는 10개 패턴을 같은 시간축에서 반복 재생하며, 보드의 재생 버튼으로 전체 흐름을 함께 멈추거나 다시 볼 수 있습니다.

왜 "패턴"으로 외우는가

Big-O는 입력 크기 n이 커질 때 연산량이 어떤 추세로 늘어나는지를 나타냅니다. 코드를 한 줄씩 세지 않아도, 루프와 재귀의 모양만 보면 대부분의 복잡도를 추정할 수 있습니다. 면접에서 마주치는 코드의 대다수는 아래 10가지 형태 중 하나이거나 그 조합입니다.

읽는 순서는 빠른 것부터 느린 것 순입니다: O(1) → O(log n) → O(n) → O(n + m) → O(n log n) → O(n²) → 지수 → 팩토리얼.

1. 해시 조회 — O(1)

해시 테이블은 키에 해시 함수를 적용해 저장 위치를 바로 계산합니다. 어딘가를 순회하며 찾는 게 아니라 도착 지점을 즉시 알아내므로, 이미 만들어진 해시 테이블의 조회는 입력이 아무리 커져도 평균 연산 횟수가 일정합니다. 단, 아래처럼 인덱스를 처음 만드는 작업은 전체 원소를 한 번 읽으므로 O(n)이고, 그 뒤의 각 get 조회가 평균 O(1)입니다. 해시 충돌이 한 버킷에 몰리는 최악의 경우에는 조회도 O(n)까지 밀릴 수 있다는 점도 함께 말할 수 있어야 합니다.

// 준비 단계: 전체 상품으로 인덱스를 한 번 생성 — O(n)
const priceByProduct = new Map(products.map((item) => [item.id, item.price]))

// 사용 단계: 이미 만들어진 인덱스에서 반복 조회 — 건당 평균 O(1)
const price = priceByProduct.get("P-2049")

2. 반씩 줄이는 루프 — O(log n)

반복할 때마다 남은 입력이 상수배(보통 절반)로 줄어들면 로그 시간입니다. n = 16이면 16 → 8 → 4 → 2 → 1, 단 4번이면 끝납니다. 이진 탐색이 대표적이고, "탐색 범위가 매번 절반이 된다"는 문장이 코드에 보이면 log n을 의심하면 됩니다.

let low = 0
let high = sorted.length - 1
while (low <= high) {
  const mid = Math.floor((low + high) / 2)
  if (sorted[mid] === target) break
  if (sorted[mid] < target) low = mid + 1 // 왼쪽 절반을 버림
  else high = mid - 1 // 오른쪽 절반을 버림
}

3. 단일 루프 — O(n)

원소마다 정확히 한 번씩 일을 하면 선형 시간입니다. 합계, 최댓값, 필터링처럼 "한 바퀴 돌면서 처리"하는 코드가 모두 여기에 속합니다.

let total = 0
for (const order of orders) {
  total += order.amount // 원소마다 한 번
}

4. 연속된 루프 — O(n + m)

서로 다른 입력 두 개를 차례로 순회하면 복잡도는 더해집니다. 루프가 두 개라고 반사적으로 n²라고 답하면 안 됩니다. 중첩되어 있는지, 나란히 있는지가 곱과 합을 가릅니다.

for (const user of users) markActive(user) // O(n)
for (const group of groups) refreshCache(group) // O(m)
// 나란히 두 번 → O(n + m). 곱이 아니라 합이다.

5. 루프 + 이진 탐색 — O(q log m)

질의가 q개이고 정렬된 배열의 길이가 m이라면, 루프의 몸통 안에서 매번 O(log m) 이진 탐색을 하므로 총 O(q log m)입니다. 두 크기가 함께 증가해 q = m = n으로 놓을 수 있을 때 익숙한 O(n log n)으로 단순화됩니다.

for (const query of queries) {
  // 질의 q개
  const index = binarySearch(sorted, query) // 길이 m인 배열에서 회당 O(log m)
  handle(index)
}
// 합계: O(q log m). q = m = n이면 O(n log n)

6. 분할 정복 — O(n log n)

문제를 절반씩 쪼개면 단일 원소 리프를 포함한 구조는 log₂n + 1개 레벨이지만, 리프 자체는 병합 작업을 하지 않습니다. 실제 병합은 log₂n개 단계에서 일어나고, 단계마다 전체 n을 한 번씩 처리하므로 총합은 n log n입니다. 병합 정렬이 교과서적인 예입니다. q와 m이 함께 n으로 커지는 5번 패턴과 결과는 같지만, 여기서는 "log n개 병합 단계 × 단계당 n 작업"이라는 다른 경로로 도달합니다.

function mergeSort(list: number[]): number[] {
  if (list.length <= 1) return list
  const mid = Math.floor(list.length / 2)
  return merge(mergeSort(list.slice(0, mid)), mergeSort(list.slice(mid)))
}

7. 중첩 루프 — O(n²)

바깥 루프의 원소 하나마다 안쪽 루프가 전체를 다시 돌면, 모든 쌍 (i, j)를 검사하는 것이므로 n²입니다. n이 2배가 되면 연산은 4배가 된다는 감각이 중요합니다.

for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n; j += 1) {
    compare(items[i], items[j]) // 모든 쌍
  }
}

8. 삼각형 루프 — O(n²)

안쪽 루프를 j = i + 1부터 시작하면 검사하는 쌍이 절반으로 줄어 총 n(n−1)/2번이 됩니다. 하지만 Big-O는 상수를 버리므로 여전히 O(n²)입니다. "절반이니까 더 빠른 등급 아닌가요?"라는 함정 질문에 대비하세요.

for (let i = 0; i < n; i += 1) {
  for (let j = i + 1; j < n; j += 1) {
    // j가 i 다음부터 시작
    compare(items[i], items[j]) // 중복 쌍 제거
  }
}

9. 가지 치는 재귀 — 지수 시간

재귀 호출 하나가 새 호출을 여러 개 만들면 호출 트리가 레벨마다 배수로 불어납니다. 메모이제이션 없는 피보나치가 대표적으로, 가지가 2개면 대략 O(2ⁿ) 꼴로 폭발합니다. 이 패턴을 발견하는 것 자체가 "메모이제이션이나 DP로 바꾸라"는 신호입니다.

function fib(n: number): number {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2) // 호출 하나가 호출 둘을 만든다
}

10. 순열 생성 — O(n!)

n개 원소를 나열하는 모든 순서는 n!가지입니다. 완성된 순열을 복사해 담는 비용까지 고려하면 O(n × n!)로 보는 것이 더 정확합니다. 원소가 하나 늘 때마다 경우의 수가 (n+1)배가 되는, 목록 중 가장 빠르게 폭발하는 패턴입니다.

function permutations(rest: string[], chosen: string[] = []): string[][] {
  if (rest.length === 0) return [chosen]
  return rest.flatMap((item, index) =>
    permutations(
      rest.filter((_, j) => j !== index),
      [...chosen, item],
    ),
  )
}

패턴 한눈에 보기

n이 커지면 얼마나 벌어질까

n = 1,000일 때 대략적인 연산량입니다.

표의 아래 두 줄이 보여주듯, 지수·팩토리얼 알고리즘은 "더 좋은 하드웨어"로 해결되지 않습니다. 패턴을 알아보는 눈이 곧 설계를 바꾸라는 경보 장치입니다.

출처와 크레딧

이 글의 주제 선정은 @algomasterio의 릴스에서 영감을 받았습니다. 본문 설명과 코드 예제, 인터랙티브 애니메이션은 모두 이 블로그를 위해 직접 작성·구현했으며 원본 영상의 이미지나 영상을 사용하지 않았습니다. 알고리즘 학습 자료로는 algomaster.io도 참고할 만합니다.