공간 복잡도 (Space Complexity)

공간 복잡도 (Space Complexity)

알고리즘이 실행되는 데 필요한 메모리 공간을 입력 크기의 함수로 표현한 것

목적: 메모리 사용량 분석, 공간-시간 트레이드오프, 제약 환경 대응

특징: 보조 공간, 스택 깊이, Big-O 표기

구성: 고정 공간(코드, 상수) + 가변 공간(입력, 보조 자료구조, 재귀 스택)

보조 공간(Auxiliary Space): 입력 제외한 추가 공간, 일반적으로 공간 복잡도는 보조 공간 의미

예시

• •버블 정렬: O(1) - 제자리 정렬
• •병합 정렬: O(n) - 임시 배열
• •재귀(깊이 d): O(d) - 콜 스택
• •BFS: O(V) - 큐

공간-시간 트레이드오프: 메모리 추가로 시간 단축(메모이제이션), 또는 시간 증가로 메모리 절약

적용사례: 임베디드, 메모리 제약, 캐시 최적화

비교: 공간 복잡도(메모리 사용량 측정) vs 시간 복잡도(실행 시간 측정) - 트레이드오프 관계

연관: 시간 복잡도, 메모리, 재귀, 동적 프로그래밍