공간복잡도 란?(Space Complexity)

알고리즘이 수행되는데 필요한 메모리의 총량!

공간 복잡도 계산법

총 공간요구 = 고정 공간 요구 + 가변 공간 요구
수식 : S(P) = c + Sp(n)

고정공간

입력과 출력의 횟수나 크기와 관계없는 공간을요구 즉, 코드 저장공간, 단순 변수, 고정 크기의 구조 변수, 상수

가변공간

동적으로 필요한 공간

자바스크립트에서 number 변수는 8byte를 가진다
알고리즘 테스트에서 256MB, 512MB 제한사항이 있을경우 가변공간의 확장 판단을 해서 문제를 풀어야한다.

let a = Array(1000) // 8KB
let a = Array(1000000) //8MB
let a = Array(100000000) //800MB

공간복잡도 계산

let a = 10;

a라는 변수에 10을 할당할경우 공간복잡도는 O(1)

function test(n){
   let result = 1;
   for(let i = 0 ; i <= n; i++){
    result = result + i;
   } 
return result;
}

n의 값이 5라고 가정하고 for문을 반복하여도 result와 i는 지역변수이므로 O(1)

function test(n){
 if( n > 1 ){
    return n * test(n - 1);
 }else{
   return 1;
 }
}

재귀함수에서 test()는 콜스택에 n이 1이하 일때까지 축적되어 O(n)