공간 복잡도는 알고리즘이 실행될 때 필요한 메모리 자원의 양이 입력 크기에 따라 어떻게 변하는지를 설명하는 지표이다.[1][3] 입력 자체가 차지하는 공간과 알고리즘이 추가로 쓰는 메모리를 함께 보면서, 구현이 커질수록 어떤 부담이 생기는지 예측하게 해 준다.[3][4]
1. 개요
2. 정의 및 개념
공간 복잡도는 알고리즘이 실행되는 동안 요구하는 전체 메모리 자원의 총량을 의미한다. 여기에는 입력 데이터가 차지하는 공간과 연산 과정에서 추가로 쓰는 공간이 모두 포함된다.[3][4]
보조 공간은 입력 데이터 자체를 제외하고 추가로 할당되는 임시 메모리다. 반면 공간 복잡도는 입력 공간까지 포함한 더 넓은 개념이므로, 두 용어를 구별해 쓰는 것이 중요하다.[4]
이 구분은 알고리즘의 메모리 효율을 비교할 때 특히 중요하다. 같은 문제를 풀더라도 자료를 저장하는 방식이나 재귀 호출 구조에 따라 전체 공간 요구량이 달라질 수 있기 때문이다.[1][3]
3. 빅오 표기법과의 관계
빅오 표기법은 알고리즘의 시간 복잡도와 공간 복잡도를 점근적 분석으로 표현할 때 널리 쓰이는 표기법이다. 공간 복잡도에서는 입력 크기 이 증가할 때 메모리 사용량이 어떤 상한을 갖는지 설명하는 데 사용된다.[1][2]
이 표기법은 구체적인 바이트 수를 세는 대신, 메모리 요구량의 증가율을 다룬다. 따라서 서로 다른 알고리즘이나 자료 구조를 비교할 때, 어느 쪽이 더 메모리를 효율적으로 쓰는지 판단하는 기준이 된다.[2][3]
일반적으로 공간 복잡도는 최악의 경우를 기준으로 서술된다. 이렇게 하면 실행 중 발생할 수 있는 최대 메모리 부담을 미리 가늠할 수 있다.[2][3]
4. 공간 복잡도와 보조 공간의 차이
5. 시간 복잡도와의 비교
6. 알고리즘 설계 시 고려사항
알고리즘을 설계할 때는 제한된 메모리를 어떻게 사용할지 미리 검토해야 한다. 특히 입력 규모가 커질수록 추가 공간이 급격히 늘어나는 구조는 실제 서비스에서 부담이 될 수 있다.[3][4]
설계자는 빅오 표기법을 통해 공간 사용량의 증가 경향을 점검하고, 필요한 경우 더 적은 메모리를 쓰는 자료 구조나 반복 기반 구현을 선택해야 한다. 이런 선택은 시스템의 안정성과 확장성에도 영향을 준다.[1][2]
결국 공간 복잡도는 단순한 이론값이 아니라 구현 전략의 제약 조건이다. 메모리 사용을 적절히 통제해야 프로그램이 대용량 입력에서도 안정적으로 동작한다.[3][4]