[Algorithm - Big O Notation] 코드 시간 재기 (1/4)

빅오 (Big O)란 무엇인가?

어떤 문제를 해결하기 위한 방법이 2가지 이상이 있다고 생각해보자. 하나는 for문을 사용하고 다른 방법은 문자열을 이용해서 해결한다고 가정해보자. 어떤 것이 더 좋은 코드인지 어떻게 알 수 있을까? 그때 Big O가 필요하다. 즉, 빅오(Big O)란 여러가지 코드를 서로 비교하고 성능을 평가하는 방법이다. 코드 시간 재기를 통해 그 사례를 알아보자!

 

빅오(Big O)는 코드를 평가한다.

 

 

코드 시간 재기

1에서부터 특정한 N값과 사이에 있는 모든 숫자들을 더하는 Function을 작성한다고 가정해보자. (Suppose we want to write a function that calculates the sum of all numbers from 1 up to (and including) some number n.) 만약, 3을 입력하면 6이 나온다. 

 

첫번째 해결 코드

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
    	total += i;
    }
    return total;
}

 

처음으로 생각한 방법은 Total이라는 변수를 만들고, for문을 사용하여 n 숫자까지 모든 숫자들을 차례대로 더하는 것이다. 

 

 

두번째 해결 코드

function addUpTo(n) {
	return n * (n + 1) / 2;
}​

 

두번째 해결 방법은 n을 갖고 n + 1의 값을 곱하고 2로 나눈다. 

 

 

이 두가지 방법 중 더 나은 것은 무엇을 의미하는 것일까? Faster(속도), Less Memory-intensive(메모리 사용), More readable(가독성) 등을 고려할 수 있으며 모두 중요한 요소이다. 먼저, 속도를 집중적으로 탐구해보자. 이를 측정하기 위해서는 타이밍 함수를 사용하면 된다. 아래의 코드를 살펴보자.

 

function addUpTo(n) {
	let total = 0;
    for (let i = 1; i <= n; i++) {
    	total += i;
    }
	return total;
}

let t1 = performance.now();
addUpTo(1000000000);
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} secondes.`)

 

performance.now()를 사용하는데 이는 브라우저가 이 문서를 만들어 창이 열린 시간을 알려준다. addUpTo 함수를 호출하기 전에 이 함수를 변수에 저장하고 addupto에 10억을 입력하고 호출한다. 개발자 도구 콘솔을 살펴보면 아래와 같은 결과 값이 나타나게 된다. 

 

 

 

 

function addUpTo(n) {
	return n * (n +1) /2;
}

let t1 = performance.now();
addUpTo(1000000000);
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} secondes.`)

 

다른 방식의 속도를 측정하면 아래와 같은 결과 값이 나타난다. 시간이 훨씬 짧은 것을 알 수 있다.

 

 

하지만 여기에는 몇 가지 고려해야할 사항이 있다.

첫째, 기기마다 다른 방식으로 시간을 기록하기 때문에 완전히 믿을 수가 없다. 기기 사양에 따라 다를 수도 있고 그 기계에 무엇이 실행 되고 있는지에 따라 다를 수도 있다. 물론, 그렇다고 해서 갑자기 두번째 코드보다 첫번째 코드가 더 빠르게 나올 수 있다는 것은 아니다. 

둘째, 같은 기기라도 다른 시간을 기록할 수 있다. 큰 문제는 아니지만 정확하지 않다는 것을 알려주며, 완전히 믿을 수가 없다.

셋째, 빠르게 처리되는 알고리즘의 경우 속도 측정의 정확도가 충분하지 않을 수 있다.

 

상기의 케이스의 경우 속도 측정 정확도가 충분하지 않을 수 있다. 또한, 매번 어떤게 더 빠른지 알기 위해서 테스트를 실행하기 힘들다. 그렇다면 시간을 측정하지 않고 어느 코드가 더 좋은지 어떻게 평가할 수 있을까? 이럴때 빅오 표기법을  사용하게 된다.