서론
저번까지 Big O notation의 시간복잡도에 대해서 이야기를 해 보았다.
입력값이 커지면 알고리즘이 얼마나 많은 시간이 소요되는지 그 전체적인 추세를 알아보는 방법에 대해서 알아보았다.
이번에는 공간 복잡도이다! 이번에 주목할 것은 알고리즘이 메모리를 얼마나 많이 사용하는지이다.
본론
시간복잡도를 표기했던것과 같이 공간복잡도도 같은 방식으로 표현 할 수 있다.
여기에는 몇가지 규칙들이 있는데, 그 규칙들은 다음과 같다.
- boolean, number, null, undefined 의 공간은 자바스크립트 내에서 불변한다.
- 문자열은 O(n)의 공간을 필요로 한다.
- reference type, Object, arrays 도 마찬가지로 O(n)의 공간을 필요로 한다.
이전 글에서 사용했던 코드를 가져와서 봐 보자.
<script>
function addAll(n){
var total = 0;
for(var i = 0; i<=n; i++){
total += i;
}
return total;
}
console.log(addAll(n));
</script>이 알고리즘은 시간 복잡도가 O(n)인 알고리즘이다. 그렇다면 공간 복잡도는 어떻게 될까?
여기서는 total이라는 상수의 변수만이 만들어진다.
그리고 공간복잡도의 법칙에서 number은 불변하는 공간이다.
100, 10000, 100000이 모두 같은 메모리를 차지하고 있는 것이다.
그러니 이 알고리즘에서 공간복잡도는 상수공간복잡도( O(1) )이 된다.
위의 알고리즘은 결과적으로 시간복잡도는 좋은 편이 아니지만, 메모리를 차지하는 공간복잡도는 좋은 알고리즘인 것이다.
이전까지는 막연하게 좋은 코드란 for문이나 while같은 루프코드를 사용하지 않는 알고리즘이라고만 외우고 있었다. 하지만 그게 '왜'인지 이유는 잘 모르고 알고리즘을 짜 왔었다. Big O를 공부하게 되면서 효율적인 알고리즘을 만들기 위해서는 어떤 것을 고려해야하는지 그 기준을 세울 수 있게 된 것 같다. 또 실무에서 협업을 할 때 다른 팀과 대화를 위해서 꼭 알아두어야 하는 개념이라고 생각한다.
참고
