서론
오늘부터 Udemy에서 강의를 듣기 시작했다!
첫 스타트는 자바스크립트의 알고리즘과 자료구조에 대한 강의를 듣기 시작했는데 앞으로 한동안은 여기서 공부한 것들을 정리할 것 같다. 그 첫 스타트가 Big O에 대한 정리이다.
위에는 잡담 이제 진짜 서론
좋은 코드란 무엇인가? 처리가 빠른 코드? 메모리를 적게 사용하는 코드? 잘 읽히는 코드??
이 셋 다 모두 좋은 코드의 조건이며, 잘 읽히는 것보다는 처리가 빠르고 메모리 사용량이 적은 것이 기능적으로 우선시 된다. 그럼 그런 코드를 구현하기 위해서 우리는 내가 작성한 코드를 실행할때 얼마나 처리시간이 걸리는지, 메모리를 얼마나 잡아먹는지를 알 수 있어야 한다.
오늘 이야기 하고자하는 Big O는 그 중 처리시간에 대한 표기법이다.
본론
1부터 N까지의 연속된 숫자의 합을 구하시오.
이 문제를 봤을때 우리는 여러가지 해결법을 떠올릴 수 있다.
이 글에서는 그 중 두 가지만 뽑아 다룰 예정이다.
첫번째 해결법
많은 사람들이 바로 떠올렸고 나 또한 이 문제를 보자마자 이 방식으로 접근해 문제를 해결했다.
그것은 바로 for문을 이용한 방법이다.
<script>
function addAll(n){
var total = 0;
for(var i = 0; i<=n; i++){
total += i;
}
return total;
}
console.log(addAll(n));
</script>두번째 해결법
이 해결법은 for문을 사용하지 않고 공식을 이용하는 방식으로 접근을 했다.
<script>
function addAll2(n){
return n*(n+1)/2;
}
console.log(addAll2(n));
</script>두 방법 모두 제대로 기능하고 작은 숫자를 대입했을때는 큰 차이가 없지만, 큰 숫자를 대입하기 시작하면 처리시간에서 차이를 보이기 시작한다. timing function을 이용하면 그 시간차이를 가시적으로 확인할 수 있다.
왜 그런것일까?
연산의 갯수에 차이가 있기 때문이다. 연산의 갯수가 많으면 많을수록 처리는 더 오래 걸린다. 연산에는 +, =, *, - 등등이 포함되며, 첫번째 해결법에서는 for 루프를 사용하며 n만큼 더 연산을 하게 된다. n의 증가에 비례해서 연산이 늘어나는 것이다. 그러나 두번째 해결법에서는 n이 끝없이 늘어나더라도 연산의 갯수는 일정하다. 그렇기 때문에 숫자가 커질수록 둘의 차이는 더 커질 수 밖에 없다.
어떤 알고리즘이 더 효율적인지 알기 위해서 연산갯수를 하나하나 셀 수 없는 노릇이다. 그래서 전체적인 처리의 추세를 나타낸 표기법이 바로 Big O 표기법이다.
Big O 표기법으로 첫번째 해결책과 두번째 해결책을 표현하면 다음과 같다.
첫번째 - O(n)
두번째 - O(1)
맛보기로 여기까지 더 자세한 내용은 내일 다시 이어가도록 하겠다.
참고
