[CS] 공간 복잡도

공간 복잡도(Space Complexity)는 알고리즘이 실행되는 동안 얼마나 많은 메모리를 사용하는지를 측정하는 지표입니다. 시간 복잡도와 함께 알고리즘의 효율성을 평가하는 데 중요한 역할을 하며, 특히 메모리 제약이 있는 환경에서 최적화가 필요할 때 고려됩니다.

1. 공간 복잡도의 정의

공간 복잡도는 알고리즘이 입력 크기 𝑛에 따라 얼마나 많은 메모리를 사용하는지를 나타냅니다. 여기에는 입력 데이터의 저장 공간뿐만 아니라, 변수, 배열, 재귀 호출 스택 등 추가적으로 필요한 메모리 공간도 포함됩니다.

2. 공간 복잡도를 구성하는 요소

공간 복잡도는 다음 두 가지 주요 요소로 구성됩니다:

• 고정 공간 (Fixed Part): 입력 크기와 상관없이 항상 일정한 메모리 공간을 사용하는 부분입니다.

  • 예: 변수 선언, 상수 등.

• 가변 공간 (Variable Part): 입력 크기에 따라 달라지는 메모리 공간입니다.

  • 예: 배열, 동적 할당, 재귀 호출 스택 등.

3. 공간 복잡도의 표기법: Big-O 표기법

공간 복잡도도 시간 복잡도와 마찬가지로 Big-O 표기법으로 표현합니다.

Big-O 표기	의미	예시
O(1)	상수 공간: 입력 크기와 관계없이 일정한 메모리 사용	변수 하나 사용, 단순 연산
O(n)	선형 공간: 입력 크기에 비례한 메모리 사용	배열, 리스트
O(n^2)	이차 공간: 입력 크기의 제곱에 비례한 메모리 사용	2차원 배열

4. 공간 복잡도의 계산 방법

예시 1: 단순 변수 사용

int a = 10;
int b = 20;
int sum = a + b;

• 이 경우, 변수 3개에 대한 고정된 공간이 필요하므로 공간 복잡도는 O(1)입니다.

예시 2: 배열 사용

int[] arr = new int[n];

• 배열의 크기가 입력 n에 따라 달라지므로, 공간 복잡도는 O(n)입니다.

예시 3: 재귀 함수

void recursiveFunction(int n) {
    if (n == 0) return;
    recursiveFunction(n - 1);
}

• 재귀 호출이 n번 발생하며, 호출마다 스택에 함수의 상태가 저장되므로 공간 복잡도는 O(n)입니다.

5. 공간 복잡도와 시간 복잡도의 관계

공간 복잡도와 시간 복잡도는 종종 트레이드오프 관계에 있습니다. 즉, 하나를 최적화하면 다른 하나가 증가할 수 있습니다.

상황	설명	예시
시간 최적화	더 많은 메모리를 사용하여 실행 시간을 줄임	캐싱, 메모이제이션
공간 최적화	적은 메모리를 사용하여 실행하지만 시간이 더 걸림	In-place 알고리즘

6. 공간 복잡도의 실제 활용 사례

• 정렬 알고리즘
  • 병합 정렬 (Merge Sort): 추가 메모리가 필요하므로 공간 복잡도가 O(n)입니다.
  • 퀵 정렬 (Quick Sort): In-place 정렬로 공간 복잡도가 O(logn)입니다.
• 동적 프로그래밍
  • 메모이제이션(memoization)을 사용하여 중복 연산을 줄이지만, 테이블을 저장하기 위한 메모리가 필요합니다.
• 그래프 탐색
  • DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)의 공간 복잡도는 각각 재귀 스택과 큐의 크기에 따라 결정됩니다.

7. 공간 복잡도 최적화 방법

• In-place 알고리즘 사용
  • 추가 메모리 공간을 사용하지 않고 입력 데이터 자체를 수정합니다.
• 재귀 대신 반복문 사용
  • 재귀 호출로 인한 스택 오버헤드를 제거합니다.
• 동적 메모리 할당 최소화
  • 필요한 메모리만 동적으로 할당하여 낭비를 줄입니다.