1. 빅오 (Big-O) 표기법

빅오 표기법은 이 알고리즘 혹은 이 코드를 비교할때 얼마나 효율적인지 판단할 수 있는 지표가 된다.

예시) 지진이 얼마나 강도가 높았는지 혹은 쌨는지 판단하기 위해 리히터 규모로 판단을 할 수 있다.

리히터 규모.png

  1. 시간 복잡도 ( time complexity )

입력의 크기에 따라 이 알고리즘을 처리하는데 걸리는 시간을 판단한다.

ex) 1 부터 n 까지의 합을 구하는 알고리즘

  1. O(1)

n(입력)의 크기와 상관없이 같은 시간을 유지한다. (해쉬, 객체에서 key로 찾기)

let total = 0;

total = n * (n+1) / 2;

n의 크기가 10이건 100000이라도 연산은 총 3번밖에 안일어난다.

  1. O(n)

n의 크기에 의존하여 n 만큼의 시간이 걸린다. 보통은 기본 적인 for 반복문이 O(n)이다.

연산이 몇번 들어갔는지 중요하지 않다…. 결국 연산 * n 만큼 n의 크기에 따라 실행 될것이기 때문.

// 대표적인 O(n)이다.
let total = 0;
for(let i = 0; i<=n; i++){
	total += i;
}
console.log(total);

반복문이 별개로 2번 돌면 2n 이겠지만… n앞의 상수는 무시한다. n으로 본다.

// 대표적인 O(n)이다.
let total = 0;
for(let i = 0; i<=n; i++){
	total += i;
}

// 대표적인 O(n)이다.
let total = 0;
for(let i = 0; i<=n; i++){
	total += i;
}
console.log(total);