공간 복잡도란?

공간 복잡도: 알고리즘의 메모리 사용을 이해하기

공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리 양을 측정하는 개념이다.

이는 알고리즘의 효율성을 평가하는 중요한 척도 중 하나로, 특히 대규모 데이터를 처리하거나 메모리가 제한된 환경에서 중요하다.

공간 복잡도에 영향을 미치는 요소

• 변수
• 자료 구조(Data structure)
• 함수 호출(Function call)
• 할당(Allocation)

공간 복잡도의 주요 특징

1. 입력 크기에 따른 측정
   공간 복잡도는 일반적으로 입력 데이터의 크기(n)에 따라 표현됨
2. 빅오 표기법 사용
   O(1), O(n), O(n^2) 등의 표기법으로 나타냄
3. 시간 복잡도와의 관계
   때로는 추가 메모리를 사용하여 실행 시간을 단축할 수 있다
4. 고정 공간과 가변 공간
   알고리즘이 사용하는 메모리를 고정 공간(입력 크기와 무관)과 가변 공간(입력 크기에 따라 변화)으로 구분할 수 있다

공간 복잡도의 종류

상수 공간 O(1): 입력 크기와 관계없이 일정한 양의 메모리를 사용

def find_max(arr):
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

이 함수는 입력 배열의 크기와 관계없이 단일 변수 max_val만을 사용하므로 O(1) 공간 복잡도를 가진다.

선형 공간 O(n): 입력 크기에 비례하여 메모리 사용량이 증가

def duplicate_array(arr):
    new_arr = []
    for num in arr:
        new_arr.append(num)
    return new_arr

이 함수는 입력 배열의 크기에 비례하는 새 배열을 생성하므로 O(n) 공간 복잡도를 가진다.

로그 공간 O(log n): 입력 크기의 로그에 비례하여 메모리를 사용

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

이진 탐색은 재귀적으로 구현될 때 호출 스택에 O(log n)의 공간을 사용함

이차 공간 O(n^2) : 입력 크기의 제곱에 비례하는 메모리를 사용

def create_matrix(n):
    matrix = [[0 for _ in range(n)] for _ in range(n)]
    return matrix

이 함수는 n x n 크기의 2차원 배열을 생성하므로 O(n^2) 공간 복잡도를 가진다.

시간 복잡도(Time Complexity) vs 공간 복잡도(Space Complexity)

특성	시간 복잡도	공간복잡도
정의	알고리즘 실행에 필요한 시간	알고리즘 실행에 필요한 메모리공간
측정 대상	연산 횟수	메모리 사용량
최적화 목표	실행 속도 개선	메모리 효율성 개선
일반적인 표현 예시	O(1), O(log n), O(n), O(n log n), O(n²)	O(1), O(n), O(n²)
영향 요인	입력 크기, 알고리즘 로직	입력 크기, 자료 구조 선택
분석 중점	루프, 재귀 호출, 연산 횟수	변수, 자료 구조, 함수 호출 스택
트레이드오프 관계	공간을 더 사용하여 시간을 줄일 수 있음	시간을 더 사용하여 공간을 줄일 수 있음
표기법	빅오(Big O) 표기법