시간복잡도, Big O 표기법

 

시간복잡도란? 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도

Big O 표기법, 성능비교를 위한 상대적인 표기법 중 하나 

 

빠름  O(1) <  O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)  느림

 

n이 1024라고 가정하였을때

O(n)은 1024번 루프

O(logn)은 10번 루프

즉, 상수시간에 가까울수록 시간을 대폭 절약하여 성능향상을 시킬 수 있다.

 

*CS에서 log 밑에 생략되어 있으면 보통 2 

 

 

O(1) 상수시간

O(logn) 로그시간

O(n) 선형시간

O(nlogn) 선형로그시간

O(n^2) 이차시간

O(2^n) 지수시간

O(n!) 팩토리얼시간

 

//O(n)일때 
for(let i=0; i<n; i+=1) {
}

//O(log n)일때 
for(let i=1; i<=n; i*=2) {
}

//O(nlog n)일때 
for(let i=0; i<n; i+=1) {
  for(let j=0; j<=n; j*=2) {
  }
}

//O(n^2)일때 
for(let i=0; i<n; i+=1) {
  for(let j=0; j<n; j+=1) {
  }
}

 

4가지 법칙

1. 계수법칙 상수k가 0보다 크면 생략할 수 있다.(n이 무한에 가까워질수록 k의 영향이 적어짐)

 ex) O(6n) => O(n)

 

2. 합의 법칙 

ex) O(n) + O(m) = O(n+m)

 

3. 곱의 법칙

ex) O(n) * O(m) = O(nm) , O(n) * O(n) = O(n^2)

 

4. 다항 법칙 

ex) O(6n+3m) => O(n+m) ,   상수항은 무시된다.

      O(n^2 + n) => O(n^2)      가장 큰 항외에는 무시된다.

 

 

성능측정방법

console.log("Start!!!!");
const start = new Date().getTime();

function(){
}

const end = new Date().getTime();

console.log(end - start);
console.log("Finish");


//console.time()을 활용한 방법
console.time("example");

function(){
}

console.timeEnd("example");