시간복잡도와 공간복잡도

알고리즘이 입력 크기 n에 대해 얼마나 시간이 걸리고, 얼마나 메모리를 쓰는지를 함수로 표현한 척도입니다.

왜 필요한가?

같은 문제를 푸는 두 코드:

[ 코드 A ]                  [ 코드 B ]
이중 루프로 중복 검사         정렬 후 인접 비교
n=10     → 100번             n=10     → 30번
n=1,000  → 1,000,000번        n=1,000  → 10,000번
n=1,000,000 → 1조 번       n=1,000,000 → 약 2천만 번 O

→ "동작한다"와 "쓸 만하다"는 다르다
→ 입력이 커질 때 어떻게 증가하는가? = 복잡도

머신 성능, 언어, 컴파일러 최적화는 모두 상수에 흡수됩니다. 우리가 보는 건 입력 n에 대한 증가율입니다.

점근 표기법

O(f(n))    상한 — 아무리 나빠도 이만큼
Ω(f(n))    하한 — 아무리 잘해도 이만큼
Θ(f(n))    상·하한 일치 — 정확히 이 차수
표기의미실무 사용
Big-O최악의 경우 상한가장 흔히 사용
Big-Ω최선의 경우 하한이론에서 사용
Big-Θ상한 = 하한타이트한 분석

코딩테스트·면접에서 "복잡도가 어떻게 돼?"는 거의 항상 Big-O를 묻는 것입니다.

표기 규칙

3n² + 5n + 100  →  O(n²)     // 최고차항만 남긴다
1000n           →  O(n)      // 상수 계수 무시
log₂ n, log₁₀ n →  O(log n)  // 로그 밑 무시 (상수배 차이)

자주 보는 시간복잡도

빠름 ────────────────────────────────────→ 느림
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
복잡도이름대표 예시
O(1)상수배열 인덱스 접근, 해시 조회
O(log n)로그이진 탐색, 균형 BST
O(n)선형단순 순회, 선형 탐색
O(n log n)선형로그병합/퀵/힙 정렬
O(n²)이차이중 루프, 버블/선택/삽입 정렬
O(2ⁿ)지수부분집합 완전탐색, 단순 피보나치 재귀
O(n!)팩토리얼순열 생성, 외판원 완전탐색

시간 감각 (1초 ≈ 10⁸ 연산)

n ≤ 10        →  O(n!) 가능 (순열)
n ≤ 20        →  O(2ⁿ) 가능 (비트마스크)
n ≤ 5,000     →  O(n²) 안전
n ≤ 100,000   →  O(n²) 빠듯, 보통 통과
n ≤ 1,000,000 →  O(n log n) 까지 가능
n ≥ 10⁷       →  O(n) 또는 O(log n) 만 가능

코딩테스트에서 N 제한을 보면 알고리즘이 보입니다. 거의 항상 맞습니다.

시간복잡도 예제

O(n) — 선형

int sum(int[] arr) {
    int total = 0;
    for (int x : arr) total += x;   // n번 반복
    return total;
}

O(n²) — 이중 루프

boolean hasDuplicate(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

O(log n) — 이진 탐색

int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

탐색 범위가 매 반복마다 절반:
n → n/2 → n/4 → ... → 1
반복 횟수 = log₂ n

공간복잡도

추가로 사용하는 메모리 양을 입력 크기 n의 함수로 표현합니다. 입력 자체가 차지하는 공간은 보통 제외하고, 알고리즘이 추가로 쓰는 공간만 봅니다.

공간복잡도예시
O(1)변수 몇 개만 사용 (in-place 알고리즘)
O(log n)이진 탐색의 재귀 호출 스택
O(n)배열·해시맵에 결과 누적, 깊이 n 재귀
O(n²)DP 2차원 테이블, 인접 행렬

시간 vs 공간 트레이드오프

[ 메모이제이션(DP) ]
시간 줄임 ↔ 공간 더 씀

[ in-place 정렬 ]
공간 줄임 ↔ 구현 복잡 ↑

→ 문제 제약(메모리 제한 256MB 등)을 보고 선택

헷갈리기 쉬운 포인트

재귀의 공간복잡도

재귀 함수는 호출 스택도 공간을 차지

depth=n 재귀 → 공간 O(n)
큰 입력에서 스택 오버플로 위험

평균 vs 최악

알고리즘평균최악
퀵소트O(n log n)O(n²) (정렬된 입력 + 끝 피벗)
해시맵 조회O(1)O(n) (모든 키 같은 버킷)
이진 탐색 트리O(log n)O(n) (편향 트리)

면접은 보통 최악, 실무는 평균이 더 중요한 경우도 많음.

분할상환(Amortized) 분석

ArrayList.add():
  보통       → O(1)
  배열 확장 시 → O(n)  (두 배로 늘리며 복사)

n번 연산을 평균내면:
  총 비용 ≈ 2n
  연산당 → O(1)

→ 분할상환 O(1)

실전 체크리스트

문제를 풀기 전에:
1. 입력 크기 N 확인          → 허용 가능한 복잡도 추정
2. 시간 제한 확인 (1초≈10⁸)  → O(n²)? O(n log n)?
3. 메모리 제한 확인 (256MB)  → 배열 크기 계산
4. 알고리즘 결정 → 복잡도 검산 → 구현

복잡도를 미리 계산하지 않고 구현부터 시작하면, 다 짜놓고 시간 초과로 갈아엎습니다.

핵심 정리

시간복잡도와 공간복잡도는 알고리즘이 입력 크기 n에 대해 자원을 얼마나 쓰는지를 표현하는 척도입니다. 머신 성능 같은 상수는 무시하고 증가율만 봅니다. Big-O는 최악 시나리오의 상한을 나타내며, 실무·코딩테스트의 표준 표기입니다. 자주 보는 차수는 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) 순이고, N 제한을 보면 가능한 알고리즘이 거의 결정됩니다. 공간복잡도는 추가 메모리 사용량이며, 시간과 트레이드오프 관계가 자주 나타납니다.

CSLOG에서 보기