1-3 복잡도 분석 · JUNSEOK CS study

"빨라요"가 아니라 "입력이 N배로 커지면 시간이 몇 배가 되나". 이 질문에 즉답할 수 있는 것이 목표다.

0. 복잡도라는 말부터 — 초심자용

0-1. "이 코드 빨라요?"가 의미 없는 이유

같은 코드도 내 노트북에서는 1초, 10년 된 서버에서는 10초, 요즘 최신 CPU에서는 0.1초가 걸린다. 즉 "몇 초 걸리냐"는 기계에 종속된다.

그런데 우리가 진짜 알고 싶은 건 이거다.

입력이 10배로 커지면, 실행 시간도 10배로 늘어나나? 아니면 100배? 1000배?

이 "증가 추세"는 기계가 달라져도 똑같이 유지된다. 그래서 복잡도(complexity) 는 "시간의 절대값"이 아니라 "입력 크기에 대한 증가율" 을 말한다.

0-2. 한 줄 비유

쌀 10kg을 10분에 옮기는 사람 → 100kg이면 100분 걸림 → 선형
쌀 10kg 옮기려고 매번 한 톨씩 창고 끝까지 왕복 → 100kg이면 10000분 → 이차

기계(사람)의 속도는 달라도, 전략(알고리즘) 이 같으면 증가 패턴은 같다.

0-3. 이 장에서 답할 수 있게 되는 질문

"O(n²)이 왜 그렇게 위험한가?"
"내 배열에 10만 개 들어있는데, 이 코드 괜찮나?"
"이 문제는 이 이상 빠르게 풀 수 없다"는 걸 어떻게 증명하나?
메모리도 복잡도로 따질 수 있나?

0-4. 용어 미리보기

용어	한 줄 정의
점근 표기법	입력이 아주 커졌을 때의 증가 추세를 수학적으로 쓰는 문법
빅오 O(·)	"최악이어도 이보다 빠르다" — 상한
빅오메가 Ω(·)	"아무리 빨라도 이보다 느리다" — 하한
빅세타 Θ(·)	상한과 하한이 같을 때 — 정확한 차수
시간 복잡도	입력이 커지면 연산 횟수가 어떻게 늘어나는가
공간 복잡도	입력이 커지면 메모리가 어떻게 늘어나는가

1. 왜 복잡도인가

"내 코드 1초에 10만 개 처리되는데 괜찮죠?"

1만 개 입력일 때는 괜찮았지만, 100만 개 입력에서는 100초 걸리고, 1억 개에서는 1천만 초(= 115일) 걸린다. 이것이 O(n²) 알고리즘의 함정이다. 실무에서 "왜 느리냐"는 거의 대부분 복잡도 문제다. 작은 n으로 테스트하고 배포한 뒤 큰 n에서 터진다.

2. 점근 표기법

2-1. 빅오 (Big-O): 상한

f(n) = O(g(n))   ⇔   ∃ c, n₀ : ∀ n ≥ n₀, f(n) ≤ c·g(n)

풀어 말하면, 어떤 상수 c와 기준점 n₀가 존재해, n₀ 이후로는 f(n)이 항상 c·g(n) 이하라는 뜻. "최악의 경우 이보다 더 느리지는 않다".

2-2. 빅오메가 (Big-Ω): 하한

f(n) = Ω(g(n))   ⇔   ∃ c, n₀ : ∀ n ≥ n₀, f(n) ≥ c·g(n)

"적어도 이만큼은 걸린다". 효율 정렬의 하한이 Ω(n log n)이라는 식의 증명에 쓰인다.

2-3. 빅세타 (Big-Θ): 상하한 일치

f(n) = Θ(g(n))   ⇔   f = O(g) ∧ f = Ω(g)

정확한 차수. 일상 대화에선 "O(n log n)"이라고 해도 대개 세타를 의미한다.

2-4. 실무 규칙

"빅오"만 말해도 99% 의사소통 가능
면접에서 "빅오의 정의가 뭐죠?"라는 질문이 나오면 상한의 수학적 정의를 말할 수 있어야 한다
평균/최악/최선을 구분해야 하는 경우에 정의가 필요하다 (예: 해시 테이블)

3. 대표 복잡도 직관

3-1. 차수표

복잡도	이름	예시	n = 10⁶일 때
O(1)	상수	해시 조회	즉시
O(log n)	로그	이분 탐색	~20 연산
O(n)	선형	배열 순회	10⁶ 연산
O(n log n)	선형 로그	효율 정렬	~2 × 10⁷
O(n²)	이차	이중 루프	10¹² ← 터짐
O(2ⁿ)	지수	부분집합 생성	n=30 이미 10⁹
O(n!)	팩토리얼	순열 생성	n=20도 터짐

3-2. "몇 초 안에?" 감각

대략 1초에 10⁸ 연산 수행한다고 잡는다 (JS는 그보다 좀 느림).

n = 10⁴, O(n²) = 10⁸ → 간당간당
n = 10⁵, O(n²) = 10¹⁰ → 터짐, O(n log n)이어야 함
n = 10⁶, O(n log n) = 2 × 10⁷ → 문제없음
n = 10⁷, O(n) 이하로 가야 함

"입력 크기 → 허용 복잡도" 매핑을 몸에 익혀야 코테에서 방향을 빨리 잡는다.

3-3. 상수 무시의 함정

O(n)과 O(100n)은 같은 차수지만 실제 성능은 100배 차이다. 빅오는 차수만 본다. 실전에서는 상수도 중요하지만, 입력이 커질수록 차수가 지배한다.

O(n²)인 상수 1짜리 알고리즘 vs O(n)인 상수 1000짜리 알고리즘
- n = 100:  O(n²) = 10⁴,  O(n) = 10⁵  ← 작은 n에선 O(n²) 승
- n = 10⁴: O(n²) = 10⁸,  O(n) = 10⁷  ← 큰 n에선 O(n) 승

4. 여러 항이 있을 때

f(n) = 3n² + 100n + 1000  →  O(n²)

가장 큰 차수만 남긴다. 계수는 무시. 낮은 차수 항도 무시.

왜인가: n이 충분히 커지면 n² 항이 다른 항을 압도한다. n = 10000이면 3n² = 3×10⁸, 100n = 10⁶, 1000 — 앞 항이 1000배 이상 크다.

5. 분할상환 분석 (Amortized Analysis)

5-1. 개념

"평균적 비용". 대부분의 연산이 싸고, 가끔 비싼 연산이 있을 때, 전체적으로 평균을 내면 싼 경우.

5-2. `Array.push`의 진짜 복잡도

JS 엔진은 동적 배열을 쓴다. 배열이 꽉 차면 2배 크기로 새 배열을 할당하고 전부 복사한다. 복사는 O(n)이지만, 대부분의 push는 O(1)이다.

capacity 4 → push 3번: O(1) × 3
capacity 4 → push 4번째: O(1)
capacity 4 → push 5번째: 재할당! O(5)
capacity 8 → push: O(1) × 3
capacity 8 → push 8번째: O(1)
capacity 8 → push 9번째: 재할당! O(9)
...

n개를 push하면 총 비용은:

n (O(1) 개별 비용) + (4 + 8 + 16 + ... + n) (재할당 비용)
= n + 2n
= O(n)

전체가 O(n)이므로 **한 번 push의 분할상환 비용은 O(1)**이다.

5-3. 2배 확장이 아닌 1.5배라면?

2배: 너무 빨리 커짐, 메모리 낭비
1.5배: 메모리 재사용에 유리하다는 주장이 있음 (Facebook folly가 1.5배)
1.25배: 낭비 적음, 복사가 잦음

JS 엔진마다 다르며 실무에서 직접 튜닝할 일은 거의 없다.

6. JS 내부의 숨은 복잡도

6-1. 정렬

Array.prototype.sort()는 Timsort (Chrome V8 기준, 2018년부터). 평균 O(n log n), 안정 정렬.

Timsort = 머지 정렬 + 삽입 정렬의 하이브리드
이미 부분적으로 정렬된 부분("run")을 감지해 그대로 활용
실전 데이터에서 매우 빠름

6-2. 문자열 검색

"foobarbaz".includes("bar");    // true
"foobarbaz".indexOf("bar");     // 3

V8의 구현은 입력 크기에 따라 다른 알고리즘을 선택한다 — 짧은 패턴에는 단순 선형 검색, 긴 패턴에는 Boyer-Moore-Horspool 변종. 일반적으로 O(n + m) 또는 O(n·m). KMP처럼 수학적으로 우아한 건 거의 안 쓴다.

6-3. 선형 탐색의 함정

// 배열에서 중복 체크 - O(n²)
arr.filter((x, i) => arr.indexOf(x) === i);

// Set 사용 - O(n)
[...new Set(arr)];

이 차이가 n = 10⁵에서 100초 vs 0.1초 차이로 나타난다.

6-4. 객체 순회

Object.keys(obj);     // O(n)
Object.entries(obj);  // O(n)

조회 자체는 O(1)이지만, 전체 순회는 O(n). 작은 객체는 문제없지만 수만 개 키가 있는 객체의 반복 순회는 피할 것.

7. 복잡도를 추론하는 규칙

7-1. 순차 실행: 더하기

function f(n) {
  for (let i = 0; i < n; i++) { /* ... */ }   // O(n)
  for (let j = 0; j < n; j++) { /* ... */ }   // O(n)
}
// 합: O(n + n) = O(n)

7-2. 중첩 반복: 곱하기

function f(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) { /* ... */ }
  }
}
// O(n × n) = O(n²)

7-3. 반복 안에서 절반씩 줄기: log

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
// 매 반복마다 범위가 절반 → O(log n)

7-4. 재귀: 점화식

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // T(n/2)
  const right = mergeSort(arr.slice(mid));     // T(n/2)
  return merge(left, right);                   // O(n)
}
// T(n) = 2T(n/2) + O(n)  →  O(n log n)

이를 Master Theorem으로 일반화할 수 있지만, 코테 수준에선 대표 점화식 3개만 외워두면 된다.

T(n) = T(n/2) + O(1) → O(log n)
T(n) = 2T(n/2) + O(n) → O(n log n)
T(n) = T(n-1) + O(n) → O(n²)

8. 공간 복잡도

시간만큼 중요하지만 종종 간과된다.

// O(1) 공간 - in-place
function reverseInPlace(arr) {
  for (let i = 0; i < arr.length / 2; i++) {
    [arr[i], arr[arr.length - 1 - i]] = [arr[arr.length - 1 - i], arr[i]];
  }
}

// O(n) 공간 - 새 배열
function reverseCopy(arr) {
  return [...arr].reverse();
}

재귀는 콜 스택 공간도 먹는다. factorial(n)은 O(n) 공간.

연습 문제

f(n) = 5n³ + 20n² + n log n + 100을 빅오로 표현하라.

다음 함수의 시간 복잡도를 분석하라.

function mystery(n) {
  let count = 0;
  for (let i = 1; i < n; i *= 2) {
    for (let j = 0; j < i; j++) count++;
  }
  return count;
}

Array.push가 분할상환 O(1)인 이유를 2배 확장 전략으로 설명하라.
배열 중복 제거를 filter + indexOf로 구현했을 때와 Set으로 구현했을 때, n = 10⁵에서의 예상 실행 시간 차이를 계산하라.
T(n) = 3T(n/2) + O(n²)의 복잡도를 구하라. (힌트: Master Theorem)

합 = 1 + 2 + 4 + 8 + ... + n/2 + n
   = 2n - 1
   = O(n)

"외부 log n × 내부 최대 n = O(n log n)"이라 오답하기 쉬운 문제. 실제로는 내부 루프의 합이 등비급수로 O(n).

3. Array.push 분할상환

배열 크기가 1 → 2 → 4 → 8 → ... → n이 되는 동안 재할당 비용은 1 + 2 + 4 + ... + n = 2n - 1. 개별 push의 O(1) 비용과 합쳐도 총 O(n). n번 push 평균은 O(1).

핵심: "가끔 비싼 연산"의 비용이 "자주 싼 연산"의 총합으로 상쇄됨.

4. 중복 제거 비교

filter + indexOf: O(n²) = (10⁵)² = 10¹⁰ 연산 → 100초 이상
Set: O(n) = 10⁵ 연산 → 0.001초

차이 10만 배.

5. Master Theorem

T(n) = a·T(n/b) + O(n^d). a=3, b=2, d=2.

log_b a = log₂ 3 ≈ 1.58
d = 2 > 1.58이므로 Case 3: T(n) = O(n^d) = O(n²)

체크리스트

이전: 1-2. 이산수학 핵심 | 다음: 1-4. 배열·문자열·해시

복잡도 분석