빅오 표기법이 입력(매개변수)에 따라 변화되는 시간의 관계에 대해서 측정한 것이라면, 공간 복잡도는 입력에 따라 얼마나 공간(memory)가 늘어나는지를 측정한다.
1. constant space(상수 공간)
- booleans
- numbers
- undefined
- null
2. O(n) 공간
- String(문자열의 길이에 따라)
- Array(배열의 길이에 따라)
- Object(객체의 키 갯수에 따라)
=> 문자열의 길이가 2인 String은 문자열의 길이가 1인 String보다 공간을 두배 차지
결국 좋은 알고리즘을 짜기 위해서는, 빅오 표기법에 따라 입력이 증가함에 따라 변화하는 시간 관계만 고려할 것이 아니라, 공간 복잡도가 얼마나 늘어나는지에 대한 부분도 고려해야 할 것이다.
즉, 실행 시간이 짧아도 공간 활용도가 늘어날 경우보다 실행 시간도 짧고 공간 활용도도 좋은 알고리즘을 선택해야 할 것이다.
Potentialist