Data Structure (0) 시간·공간 복잡도 분석

Big-O 계산 방법 완전 정리

알고리즘 성능을 측정하는 Big-O 표기법의 계산 방법을 체계적으로 정리한다. 코드 패턴별 복잡도 읽는 법, 재귀 점화식, 분할 상환 분석까지 다룬다.

Engineering
Data Structure
저자

Kwangmin Kim

공개

2023년 01월 17일

1 개요

Big-O 표기법은 알고리즘의 효율성을 입력 크기 N에 따른 연산 횟수의 증가율로 나타내는 점근적 표기법이다. 코딩 테스트에서는 “이 코드가 시간 제한 안에 통과할 수 있는가”를 판단하는 핵심 도구다.

실용 기준: 1초에 처리 가능한 연산 횟수
  • 기준: 초당 약 1억 번 (10^8) 연산
  • N = 10^6: \(O(N)\) → 1초 이내, \(O(N^2)\) → 10^12 → 시간 초과
  • N = 10^3: \(O(N^2)\) → 10^6 → 통과, \(O(N^3)\) → 10^9 → 위험
  • N = 300: \(O(N^3)\) → 2.7×10^7 → 통과

2 Big-O 등급 비교

등급 표기 N=10 N=100 N=1000 대표 알고리즘
상수 \(O(1)\) 1 1 1 해시 조회, 배열 인덱스
로그 \(O(\log N)\) 3 7 10 이진 탐색, 힙 연산
선형 \(O(N)\) 10 100 1,000 선형 탐색, 배열 순회
선형로그 \(O(N \log N)\) 30 700 10,000 합병 정렬, 힙 정렬
이차 \(O(N^2)\) 100 10,000 10^6 버블 정렬, 이중 루프
삼차 \(O(N^3)\) 1,000 10^6 10^9 Floyd-Warshall
지수 \(O(2^N)\) 1,024 10^30 10^301 완전 탐색(소규모만)
팩토리얼 \(O(N!)\) 3.6M 엄청남 불가 순열 완전 열거

직관: \(O(1) < O(\log N) < O(N) < O(N \log N) < O(N^2) < O(2^N) < O(N!)\)

3 코드 패턴별 복잡도 읽는 법

3.1 규칙 1: 단일 루프 → \(O(N)\)

# 단일 for 루프: N번 반복 → O(N)
for i in range(n):          # n번
    print(i)                # O(1) 연산

# 상수 배수는 무시: 3n → O(N)
for i in range(n):          # n번
    print(i)                # O(1)
    print(i * 2)            # O(1)
    print(i ** 2)           # O(1)
# 총 3n번이지만 Big-O는 O(N) — 최고차 항의 계수는 버린다

3.2 규칙 2: 중첩 루프 → \(O(N^k)\) (k = 중첩 깊이)

# 이중 루프: N×N = O(N²)
for i in range(n):           # n번
    for j in range(n):       # n번
        print(i, j)          # O(1)
# 총 n² → O(N²)

# 단, 내부 루프 범위가 i에 의존하면 달라진다
for i in range(n):           # n번
    for j in range(i):       # 0, 1, ..., n-1번 (평균 n/2)
        print(i, j)
# 총 0+1+2+...+(n-1) = n(n-1)/2 → O(N²) (계수 1/2 무시)

# 다른 변수의 중첩 루프
for i in range(n):           # n번
    for j in range(m):       # m번
        print(i, j)
# O(N×M)

3.3 규칙 3: 반씩 줄어드는 루프 → \(O(\log N)\)

# 매 반복마다 탐색 범위가 절반이 되면 O(log N)
i = n
while i > 1:
    print(i)
    i //= 2       # n → n/2 → n/4 → ... → 1  (log₂N 번)
# O(log N)

# 이진 탐색
left, right = 0, n - 1
while left <= right:          # 최대 log₂N 번 반복
    mid = (left + right) // 2
    if arr[mid] == target:
        break
    elif arr[mid] < target:
        left = mid + 1        # 탐색 범위 절반 제거
    else:
        right = mid - 1       # 탐색 범위 절반 제거
# O(log N)

3.4 규칙 4: 내장 함수의 복잡도 고려

arr = [3, 1, 4, 1, 5, 9]

# 이것들은 O(1)처럼 보이지만 실제로는 다르다
arr.sort()              # O(N log N) ← 정렬!
sorted(arr)             # O(N log N)
arr.index(5)            # O(N) ← 선형 탐색
5 in arr                # O(N) ← 선형 탐색
5 in set(arr)           # O(1) ← 해시 조회 (단, set 생성은 O(N))

# 이중 루프처럼 보이지만 다른 경우
for i in range(n):
    arr.sort()          # O(N log N) × n번 = O(N² log N) ← 주의!

for i in range(n):
    if i in set_a:      # set 조회는 O(1) → 전체 O(N)
        pass

3.5 규칙 5: 여러 단계의 합산 — 더 큰 쪽이 지배

# 순차 실행은 최대값
def f(arr):
    arr.sort()                          # O(N log N)
    for i in range(len(arr)):           # O(N)
        print(arr[i])
# O(N log N) + O(N) = O(N log N)  ← 더 큰 항이 지배

def g(arr, matrix):
    for x in arr:                       # O(N)
        print(x)
    for i in range(len(matrix)):        # O(M²)
        for j in range(len(matrix)):
            print(matrix[i][j])
# O(N) + O(M²) = O(N + M²)  ← N과 M이 독립이면 그대로 유지

4 재귀 함수의 복잡도 — 점화식으로 분석

재귀 함수의 복잡도는 점화식(Recurrence Relation) 으로 표현한 뒤 풀어야 한다.

4.1 단순 선형 재귀 → \(O(N)\)

def sum_recursive(n):
    if n == 0:
        return 0
    return n + sum_recursive(n - 1)   # T(n) = T(n-1) + O(1)

# 점화식: T(n) = T(n-1) + 1
# 전개:   T(n) = T(n-2) + 1 + 1 = T(n-k) + k
# n=k일 때 종료: T(n) = T(0) + n = O(N)

4.2 이진 분할 재귀 → \(O(\log N)\)

def binary_search(arr, lo, hi, target):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, mid+1, hi, target)  # T(n) = T(n/2) + O(1)
    else:
        return binary_search(arr, lo, mid-1, target)

# 점화식: T(n) = T(n/2) + 1
# 전개:   T(n) = T(n/4) + 1 + 1 = T(n/2^k) + k
# n/2^k = 1 → k = log₂n
# T(n) = O(log N)

4.3 분할 정복 재귀 → \(O(N \log N)\)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # T(n/2)
    right = merge_sort(arr[mid:])  # T(n/2)
    return merge(left, right)      # O(n) — 두 정렬 배열 병합

# 점화식: T(n) = 2T(n/2) + n
# 마스터 정리 Case 2: O(N log N)

4.4 지수 재귀 → \(O(2^N)\) 주의

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)
# T(n) = T(n-1) + T(n-2) + O(1) ≈ O(2^N) ← 매우 느림!

# @lru_cache로 메모이제이션하면 O(N)으로 개선된다
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
# 각 n에 대해 한 번만 계산 → O(N)

5 마스터 정리 (Master Theorem)

\(T(n) = a \cdot T(n/b) + f(n)\) 형태의 점화식을 빠르게 푸는 공식이다.

  • \(a\): 재귀 호출 수
  • \(b\): 입력 크기 분할 비율
  • \(f(n)\): 분할/병합 비용
조건 결론 예시
\(f(n) = O(n^{\log_b a - \epsilon})\) \(T(n) = O(n^{\log_b a})\) 이진 탐색: \(T(n)=T(n/2)+1\) → \(O(\log N)\)
\(f(n) = \Theta(n^{\log_b a})\) \(T(n) = O(n^{\log_b a} \log n)\) 합병 정렬: \(T(n)=2T(n/2)+n\) → \(O(N \log N)\)
\(f(n) = \Omega(n^{\log_b a + \epsilon})\) \(T(n) = O(f(n))\) —

실용적 암기: 합병 정렬의 \(T(n) = 2T(n/2) + n\) → \(O(N \log N)\) 만 외워도 코딩 테스트에서 충분하다.

6 분할 상환 분석 (Amortized Analysis)

개별 연산은 가끔 비싸지만, 전체 N번의 평균 비용은 저렴한 경우다.

6.1 Python list append의 분할 상환

arr = []
for i in range(n):
    arr.append(i)   # 대부분 O(1), 가끔 O(N) (용량 초과 시 재할당)

# 재할당 발생 횟수: 1, 2, 4, 8, ... → log₂N 번
# 재할당 총 비용: 1+2+4+...+N = 2N-1 ≈ O(N)
# N번 append의 총 비용: O(N) (재할당) + O(N) (일반) = O(N)
# → 1번 append의 분할 상환 비용: O(N)/N = O(1)

직관: 가끔 이사하는 비용을 매달 조금씩 적립한다고 생각하면 된다. 평균적으로 매달 조금씩 내는 것이지 한꺼번에 폭탄이 터지는 게 아니다.

7 공간 복잡도 분석

# O(1) 공간: 입력 외 고정 크기 변수만 사용
def sum_array(arr):
    total = 0              # 변수 1개
    for x in arr:
        total += x
    return total
# 공간: O(1) (arr는 입력이므로 제외)

# O(N) 공간: 입력 크기에 비례한 메모리
def copy_array(arr):
    result = []
    for x in arr:
        result.append(x)   # N개 원소 저장
    return result
# 공간: O(N)

# O(N²) 공간: 2D 배열
def create_matrix(n):
    return [[0] * n for _ in range(n)]   # n×n 행렬
# 공간: O(N²)

# 재귀의 공간: 호출 스택 깊이
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)   # 호출 스택 깊이 n
# 공간: O(N) (스택 프레임 n개)

메모리 기준 (Python int 기준):

변수 1개:     ~28 bytes
list 1만 개:  ~80 KB
list 100만 개: ~8 MB
list 1억 개:  ~800 MB → 메모리 초과 위험

8 코딩 테스트 시간 복잡도 전략

입력 N의 크기에 따라 허용 가능한 복잡도:

N ≤ 10       → O(N!) 가능 (순열 완전 탐색)
N ≤ 25       → O(2^N) 가능 (비트 마스킹 완전 탐색)
N ≤ 100      → O(N^3) 가능 (Floyd-Warshall)
N ≤ 1,000    → O(N^2) 가능 (버블 정렬, 이중 루프)
N ≤ 10^5     → O(N log N) 필요 (정렬, 힙, 이진 탐색)
N ≤ 10^6     → O(N) 필요 (선형 탐색, 해시)
N ≤ 10^8     → O(log N) 또는 O(1) 필요

9 관련 주제

Subscribe

Enjoy this blog? Get notified of new posts by email: