공간 복잡도(Space Complexity)란?
공간 복잡도는 알고리즘이 완전히 실행되어 결과를 산출하기까지 사용하는 메모리의 총량을 의미합니다. 여기에는 알고리즘에 입력되는 값(입력 데이터)이 차지하는 메모리도 포함됩니다.
알고리즘을 실행하려면 해당 프로그램이 반드시 주기억장치(메인 메모리)에 적재되어야 합니다. 이때 메모리는 다양한 형태로 사용되는데, 대표적인 항목은 다음과 같습니다.
- 변수(Variables): 상수값과 임시값을 포함하여 프로그램에서 사용하는 모든 변수
- 프로그램 명령어(Program Instruction): 컴파일된 코드가 저장되는 공간
- 실행 정보(Execution): 함수 호출, 실행 흐름 관리 등에 필요한 정보
보조 공간(Auxiliary Space)이란?
보조 공간은 알고리즘이 실행되는 동안 추가로 사용하는 임시 메모리 공간을 말합니다. 예를 들어 정렬 과정에서 임시 배열을 생성하거나, 재귀 호출 시 스택 메모리를 사용하는 경우가 여기에 해당합니다.
참고로 공간 복잡도와 보조 공간은 자주 혼동되지만 서로 다른 개념입니다. 공간 복잡도는 입력 데이터를 포함한 전체 메모리 사용량을 나타내며, 보조 공간은 입력을 제외한 순수하게 알고리즘 자체가 추가로 사용하는 메모리만을 의미합니다.
프로그램 실행 중 메모리 사용 구조
프로그램이 실행되는 동안 메모리는 크게 세 가지 영역으로 구분하여 사용됩니다.
- 명령어 공간(Instruction Space): 컴파일된 명령어(코드)를 메모리에 저장하기 위해 사용되는 공간입니다.
- 환경 스택(Environmental Stack): 실행 중 한 모듈(함수)이 다른 모듈이나 함수를 호출할 때, 호출 주소와 관련 정보를 저장하기 위해 사용되는 공간입니다.
- 데이터 공간(Data Space): 프로그램이 저장하는 데이터, 변수, 상수를 보관하는 공간으로, 실행 과정에서 그 내용이 지속적으로 갱신됩니다.
정리
공간 복잡도는 알고리즘의 효율성을 평가하는 중요한 척도 중 하나입니다. 시간 복잡도가 실행 속도를 다룬다면, 공간 복잡도는 메모리 자원의 효율적 사용을 다룹니다. 특히 메모리가 제한적인 환경이나 대용량 데이터를 처리하는 시스템에서는 공간 복잡도 분석이 필수적이며, 명령어 공간·환경 스택·데이터 공간의 구조를 이해하면 알고리즘 최적화에 큰 도움이 됩니다.