2025-08-24 19:52
Tags: 알고리즘
공간 복잡도
- 알고리즘이 문제를 해결하기위해 얼마나 많은 메모리 공간을 사용하는가
- 입력 데이터의 크기가 커짐에 따라 메모리 사용량이 어떻게 변하는가
- 과거엔 메모리의 가격이 겁나 비싸서 이걸 최대한 최적화 해서 1바이트라도 아껴 쓰려 노력함
- 현재는 메모리 가격이 매우 싸져서 시간 복잡도 에 비하면 중요성이 떨어졌지만 여전히 빅데이터나 제한적 환경에선 중요
공간 복잡도 구조
- 총 공간 = 고정 공간 (Fixed Space) + 가변 공간 (Variable Space)
- 고정 공간: 입력 데이터 크기와 상관 없이 항상 일정한 크기 차지하는 메모리 공간(코드 자체 크기, 상수, 단순 변수, 함수 호출 정보)
- 가변 공간: 입력 데이터의 크기에 비례하여 동적으로 변하는 메모리 공간(동적 할당 메모리, 자료 구조, 재귀 호출 스택)
표기법
시간 복잡도와 마찬가지로 점근적 표기법, 특히 빅오 표기법 사용
| 빅오 표기 | 명칭 | 설명 | 예시 |
|---|---|---|---|
| O(1) | 상수 공간 (Constant Space) | 입력 n의 크기와 상관없이 일정한 메모리만 사용 | 두 변수 교환, 단순 사칙연산 |
| O(log n) | 로그 공간 (Logarithmic Space) | 입력 n이 커져도 메모리 사용량은 매우 완만하게 증가 | 이진 탐색 (재귀 구현 시) |
| O(n) | 선형 공간 (Linear Space) | 입력 n의 크기와 정비례하여 메모리 사용량 증가 | 크기 n인 배열 생성, for 루프 |
| O(n²) | 이차 공간 (Quadratic Space) | 입력 n의 제곱에 비례하여 메모리 사용량 증가 | n x n 크기의 2차원 배열 생성 |
| O(2ⁿ) | 지수 공간 (Exponential Space) | 입력 n이 조금만 커져도 메모리 사용량이 폭발적으로 증가 | 특정 조합 문제의 재귀적 풀이 |
시간 복잡도와의 트레이드 오프 관계
- 보통 시간 복잡도와 트레이드 오프 관계 있다.
- 과거에 메모리가 비싸던 시절과 달리 지금은 시간의 가치가 압도적으로 크므로 보통 가능하면 공간을 더 써서 시간을 절약하려 한다.
- 예컨데 메모이제이션이나 캐싱이 대표적