[알고리즘] 빅오 표기법(Big-O notation) feat. JS

빅오 표기법이란?

시간 복잡도와 공간 복잡도 분석을 위한 알고리즘이다.

빅오 표기법을 사용해서 알고리즘이 얼마나 효율적인지 분석할 수 있다.

출처 : https://medium.com/better-programming/understanding-big-o-notation-c3245b8112dc

 

시간 복잡도와 공간 복잡도

시간 복잡도는 입력의 개수(n)에 따라 알고리즘의 수행 시간이 얼마인지를 나타낸다.

공간 복잡도는 알고리즘이 메모리 공간을 얼마나 필요로 하는지를 나타낸다.

 

빅오 표기법을 사용해서 일반적인 시간 복잡도 구분하기

O(1) : 상수 시간

입력에 관계없이 연산이 수행되는 알고리즘이다.

function testFN(n) {
	console.log('Big-O');
}

 

O(n) : 선형 시간

입력의 개수인 n만큼 연산이 수행되는 알고리즘이다.

function testFN(n) {
	for(let i=0; i<n; i++) {
    	console.log(i);
    }
}

 

O(n^2) : 2차 시간

입력의 개수의 n^2만큼 연산이 수행되는 알고리즘이다.

function testFN(n) {
  for(let i=0; i<n; i++) {
    console.log(i);
      for(let j=0; j<n; j++) {
    	console.log(j);
      }
  }
}

 

O(n^3) : 3차 시간

입력의 개수의 n^3만큼 연산이 수행되는 알고리즘이다.

function testFN(n) {
  for(let i=0; i<n; i++) {
    console.log(i);
    for(let j=0; j<n; j++) {
      console.log(j);
      for(let k=0; k<n; k++) {
    	console.log(k);
      }
    }
  }
}

 

O(log n) : 로그 시간

입력의 개수의 log n만큼 연산이 수행되는 알고리즘이다.

function testFN(n) {
  for(let i=1; i<n; i*2) {
    console.log(n);
  }
}

위 코드는 i가 i*2씩 증가되기 때문에 입력된 개수의 log_2n만큼 연산이 수행된다.

 

빅오 표기법 규칙으로 시간 복잡도 쉽게 계산하기

알고리즘의 시간 복잡도를 계산하는 것은 어려움이 있으니, 빅오 표기법은 기본적인 규칙을 제공하여 계산을 도와준다.

f(n)을 시간 복잡도라고 하겠다.

 

계수 법칙

입력의 개수인 n과 연관되지 않은 상수를 전부 무시하면 된다.

f(n)=5n인 알고리즘이 있다면 계수 법칙을 적용하여 O(n)=n이다.

 

합의 법칙

function testFN(n) {
  for(let i=0; i<n; i++) {
    console.log(i);
  }
  for(let j=0; j<n*5; j++) {
    console.log(j);
  }
}

위 코드를 보면 하위 알고리즘 한개는 f(n)=n, 다른 한개는 f(n)=5n일 경우 상위 알고리즘의 f(n)은  합의 법칙을 적용하여 f(n)=6n이다.

여기서 계수 법칙까지 적용하면 O(n)=n이 된다.

 

곱의 법칙

function testFN(n) {
  for(let i=0; i<n; i++) {
    console.log(n);
    for(let j=0; j<n*5; j++) {
      console.log(j);
    }
  }
}

위 코드를 보면 f(n)=n*5n이다. 곱의 법칙을 적용하면 f(n)=5n^2이 되고, 계수 법칙을 적용하면 O(n)=n^2가 된다.

 

다항 법칙

function testFN(n) {
  for(let i=0; i<n*n; i++) {
    console.log(n);
  }
}

위 코드를 보면 f(n)=n^2이다.

 

---

🎉  피드백은 언제나 환영입니다. 🎉

---