[CodingTest]공간 복잡도

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

즉, 프로그램이 필요로 하는 메모리 공간을 산출

프로그램이 요구하는 공간은 고정적인 공간과 함께 가변적인 공간을 함께 요구

가변적인 공간에 집중

가변적인 공간은 처리할 데이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향

---

공간 복잡도

---

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

팩터리얼

변수 n에 따라 변수 n이 n개가 만들어짐, n부터 1까지 스택

공간 복잡도 O(n)

---

공간 복잡도의 중요성

---

보통 시간 복잡도에 맞다면 공간 복잡도도 얼추 통과

공간 복잡도에 실패했다면, 보통 변수를 설정할 때 쓸데없는 공간을 많이 차지하도록 설정

동적 계획법(Dynamic Programming)같은 알고리즘, 하드웨어 환경 매우 한정적 -> 중요도 상승