시간·공간 복잡도

지난 글에서 알고리즘 분석의 개념을 살펴봤습니다. 이번에는 알고리즘 성능을 측정하는 두 축인 시간 복잡도와 공간 복잡도를 더 깊이 파고들겠습니다.

시간 복잡도 (Time Complexity)

시간 복잡도는 입력 크기 n이 증가함에 따라 알고리즘이 수행하는 기본 연산의 횟수가 어떻게 증가하는지를 나타냅니다. 실제 실행 시간(초)이 아니라 연산 횟수의 증가율에 집중합니다.

# O(1): 배열 인덱스 접근 — 항상 1번
def get_first(arr):
    return arr[0]

# O(n): 배열 전체 순회 — n번
def find_max(arr):
    m = arr[0]
    for x in arr:   # n번 반복
        if x > m:
            m = x
    return m

# O(n²): 중첩 루프 — n × n번
def has_duplicate(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

공간 복잡도 (Space Complexity)

공간 복잡도는 알고리즘이 실행되는 동안 사용하는 **추가 메모리(보조 공간)**의 양입니다. 입력 데이터가 차지하는 공간은 제외하고, 알고리즘이 자체적으로 필요로 하는 메모리만 계산합니다.

def reverse_in_place(arr):
    left, right = 0, len(arr) - 1  # 변수 2개만 사용
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    # 공간 복잡도: O(1) — 추가 배열 없음

def reverse_copy(arr):
    return arr[::-1]  # 길이 n의 새 배열 생성
    # 공간 복잡도: O(n)

재귀 함수는 스택 프레임을 사용하므로 공간 복잡도에 주의해야 합니다.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
# 공간 복잡도: O(n) — 깊이 n의 재귀 스택

시간-공간 트레이드오프

시간과 공간은 종종 트레이드오프(trade-off) 관계에 있습니다. 메모리를 더 사용해서 계산 시간을 줄이거나, 반대로 메모리를 아끼고 더 많은 계산을 하는 식입니다.

피보나치 수열이 대표적인 예입니다. 순수 재귀는 O(2ⁿ) 시간이지만 O(n) 메모리, 메모이제이션은 O(n) 시간과 O(n) 메모리, 반복문 방식은 O(n) 시간과 O(1) 메모리로 구현할 수 있습니다.

# 반복문 방식: O(n) 시간, O(1) 공간
def fib_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

복잡도 계산 규칙

복잡도를 구할 때 적용하는 핵심 규칙들입니다.

덧셈 규칙: 순차 실행은 각 부분의 최대값

def two_loops(arr):
    for x in arr:  # O(n)
        print(x)
    for x in arr:  # O(n)
        print(x * 2)
# 총 O(n) + O(n) = O(2n) → O(n)

곱셈 규칙: 중첩 실행은 곱

def nested(arr1, arr2):
    for x in arr1:     # O(n)
        for y in arr2: # O(m)
            print(x, y)
# 총 O(n × m) = O(nm)

지배 항 선택: 가장 빠르게 증가하는 항만 남김

T(n) = 5n³ + 100n² + 1000n + 9999 → O(n³)

공간 복잡도 주의사항: 입력 공간

보조 공간(auxiliary space)만 따집니다. 입력 배열 자체의 n개 원소는 포함하지 않습니다.

def sum_array(arr):    # 입력: n개 원소
    total = 0          # 보조: 변수 1개
    for x in arr:
        total += x
    return total
# 공간 복잡도: O(1) — 보조 공간만 계산

정리

복잡도	시간	공간
O(1)	상수 연산	고정 변수만
O(log n)	반씩 줄임	재귀 스택 log n
O(n)	1회 순회	크기 n 배열
O(n log n)	분할 정복	보조 배열
O(n²)	중첩 루프	2D 배열

• 시간·공간은 트레이드오프 관계 — 상황에 맞게 선택
• 복잡도는 지배 항만 남긴다: O(n² + n) → O(n²)
• 재귀는 스택 공간이 있음을 잊지 말 것

---

지난 글: 알고리즘 분석 입문

다음 글: 빅오 표기법

읽어주셔서 감사합니다. 😊