공간 복잡도
From Wikipedia, the free encyclopedia
알고리즘이나 자료 구조의 공간 복잡도(空間複雜度, space complexity)는 입력의 특성에 따라 계산 문제의 인스턴스를 해결하는 데 필요한 메모리 공간의 양이다. 이는 알고리즘이 완전히 실행될 때까지 필요한 메모리이다. 여기에는 입력 공간이라고 하는 입력에 사용되는 메모리 공간과 실행 중에 사용하는 다른 (보조) 메모리(보조 공간이라고 함)가 포함된다.
시간 복잡도와 마찬가지로 공간 복잡도는 와 같은 대문자 O 표기법으로 점근적으로 표현된다. 여기서 n은 공간 복잡도에 영향을 미치는 입력의 특성이다.