공간 복잡도(Space Complexity)

< 공간 복잡도(Space Complexity) >
-알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미.
-프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미.
-프로그램이 요구하는 공간은 고정적인 공간과 함께 가변적인 공간을 함께 요구합니다. 고정적인 공간은 처리할 데이터의 양에 무관하게 항상 요구되는 공간으로서, 프로그램의 성능에 큰 영향을 주지 않는다. 그러나 가변적인 공간은 처리할 데이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 줍니다.
-공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오 (Big-O) 표기법으로 표현합니다. 아래의 가장 간단한 공간복잡도 예시를 보겠습니다.

function factorial(n) {
if(n === 1) {
return n;
}
return n*factorial(n-1);
}

해당 함수의 공간 복잡도는 O(n)이라 볼 수 있습니다.

 

<중요성>
-보통 때의 공간 복잡도는 시간 복잡도보다 중요성이 떨어집니다.
-보통 시간 복잡도에 맞다면 공간 복잡도도 얼추 통과하기 때문에 알고리즘 구현 시 공간 복잡도에 실패했다면, 보통은 변수를 설정할 때 쓸데없는 공간을 많이 차지하도록 설정했을 경우가 많을 것이니 그것부터 확인해야 합니다.
-때에 따라 공간 복잡도를 중요하게 보는 경우가 있는데, 동적 계획법(Dynamic Programming)과 같은 알고리즘이나 하드웨어 환경이 매우 한정된 경우가 바로 그 경우입니다. 동적 계획법은 알고리즘 자체가 구현 시 메모리를 많이 요구하기 때문에 입력값의 범위가 넓어지면 사용하지 못하는 경우도 많고, 하드웨어 환경이 매우 한정되어 있는 경우(ex. 임베디드, 펌웨어 등)라면 가용 메모리가 제한되어 있기 때문입니다.

---

출처

코드스테이츠