공간 복잡도
이 전까지는 시간과 관련하여 알고리즘들이 얼마나 빠르게 실행하는지에대해 문제를 바라 보았다. 이걸 바로 시간 복잡도라고 한다.
이제는 입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지 하는지에 대해서 알아보자.
여전히 Big O표기법을 사용할 수 있지만 이제는 공간, 사용되는 메모리에 주목 하겠다.
공간 복잡도는 입력 되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간을 의미한다.
기본적인 규칙
- Boolean, Number, undefined, null은 javascript에서 모두 불면의 공간이다.
입력 크기와 상관없이 숫자가 1이든 1000이든 모두 같은 공간이라고 여긴다.- String은 O(n) 공간이 필요하다.
만약 n이 문자열의 길이라면, 50자가 입력되었다면 1자인 문자열보다 50배 더 많은 공간을 차지하게 된다.- reference, array, object도 대부분 O(n)이다.
공간 복잡도 Big O 예시 :
function sum(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) {
total += arr[i];
}
return total;
}let total = 0;이라는 변수는 Number이고
let i = 0;이라는 변수도 Number이다.
공간은 루프와 상관없이 이미 할당 되어 있다.
때문에 배열의 크기와 상관 없이, n이 커져도 공간 복잡도는 고정이다.
그래서 위 함수는 공간 복잡도O(1) 이다.
function double(arr) {
let newArr = [];
for (let i = 0; i < arr.length; i++) {
newArr.push(2 * arr[i]);
}
return newArr;
}
double([1, 2, 3]);double(arr)함수는 arr에 담긴 값을 2를 곱해서 돌려주는 함수이다.
새로운 배열을 만들고 루프 내에서 새로운 배열에 push하기에 n이 커질수록 공간도 비례해서 커지기 때문에 O(n)이 된다.
흠..