빅오표기법 정리 - with JS

빅오표기법

• 빅오표기법이란 무엇인가?
• 일반적인 빅오 표기법
• 빅오표기법규칙

빅오표기법이란 무엇인가?

빅오표기법이란 알고리즘의 최악의 경우 복잡도를 측정하여 나타내는 것이다.

일반적인 빅오 표기법

빅오표기법에서 n은 입력의 개수를 나타낸다.
O(1)은 입력공간에 대해 변하지 않는다. 따라서 O(1)을 상수시간이라 부른다.
O(n)은 선형시간이며 최악의 경우에 n번 연산을 수행해야하는 알고리즘에 적용된다.

O(log n)
O(nlog n)
O(n^2)
O(n^3)
O(2^n)

빅오표기법 규칙

빅오표기법의 규칙은 아래와 같고 아래의 법칙을 적용시켜 복잡도를 계산하면 된다.

• 계수법칙
• 합의법칙
• 곱의법칙
• 전이법칙
• 다항법칙

계수법칙

우선 계수법칙 부터 알아보자.
계수법칙은 단순히 입력 크기와 연관되어 있지 않은 상수를 전부 무시하면 된다.

(상수 k > 0) f(n)이 O(g(n)) 이면 kf(n)은 O(g(n)) 이다.

이렇게만 보면 조금 어렵게 다가올 수 있으니, 코드를 함께 살펴보자.

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

위의 코드는 입력된 n번에 대하여 count에 n번만큼 더하는 연산을 수행하고 있으므로
복잡도는 O(n) 이다.

그렇다면 다음나오는 코드의 시간 복잡도는 어떻게 될까?

function a(n){
  let count = 0;
  for (let i = 0; i < 5*n; i++){
  	count+=1;
  }
  return count;
}

위의 코드는 입력된 n번에 대하여 count에 n * 5번만큼 더하는 연산을 수행하고 있으므로 f(n) = 5n 이다. 하지만 빅오표기법에서는 모든 상수는 무시한다.
따라서 복잡도는 O(n) 이다.

간단히 말해서 n이 무한대 혹은 아주 큰 수와 가까워질때 4개의 연산이 더 이루어 진다고해서 크게 영향을 받거나 달라지는건 없기 때문이다.

그럼 아래의 코드의 시간복잡도는 어떻게 될지 생각해보자

function a(n){
  let count = 0;
  for (let i = 0; i < n; i++){
  	count+=1;
  }
  count+=3;
  return count;
}

위의 코드는 마지막에 한번의 연산 (count+=3) 을 더 하고 있으므로 f(n) = n + 1 이다.
하지만 이는 빅오 표기법으로 표기했을때 O(n) 이다.
이는 추가된 연산이 입력 n의 영향을 주지 않기 때문이다.

합의 법칙

이제 합의 법칙을 알아보자. 단순히 빅오를 더하면 되는 법칙이며, 주의할점은 합의 법칙을 적용한 다음엔 반드시 계수법칙을 적용해야 한다.

f(n)이 O(h(n)) 이고, g(n)이 O(p(n))이라면 f(n) + g(n)은 O(h(n) + p(n)) 이다.

이도 코드와 함께 살펴보자.

function a(n){ let count = 0; for (let i = 0; i < n; i++){ // (1) count+=1; } for (let i = 0; i < 5*n; i++){ // (2) count+=1; } return count; }

function a(n){
  let count = 0;
  for (let i = 0; i < n; i++){
  // (1)
  count+=1;
  }
  for (let i = 0; i < 5*n; i++){
  // (2)
  count+=1;
  }
  return count;
}

위의 예시에서 1번은 f(n) = n 이며, 2번은 f(n) = 5n 이므로 n + 5n = 6n 이다.
이후 계수법칙을 적용하면 O(n) = n 이 된다.
합의 법칙을 적용한 후에 반드시 계수법칙을 적용해야 됨을 잊지 말자!

곱의 법칙

곱의 법칙은 빅오가 어떤식으로 곱해지는 가에 관한 것이다.
주의할점은 곱의 법칙을 적용한 다음엔 반드시 계수법칙을 적용해야 한다.

f(n)이 O(h(n)) 이고, g(n)이 O(p(n))이라면 f(n)g(n)은 O(h(n)p(n)) 이다.

곱의 법칙은 보통 for중첩문에 보통적용된다.

function (n){
  let count = 0;
  for (let i = 0; i < n; i++){
  	count+=1
    for (let j = 0; j < 5*n; j++){
      count+=1;
    }
  }
  return count;
}

위의 예시에서 f(n) = 5n * n 즉 5n^2 를 나타낸다.
곱의 법칙을 적용하고 난 후에 계수법칙을 적용하면 O(n) = n^2 이 된다.
마찬가지로 곱의 법칙을 적용한 후에 계수법칙을 적용해야 됨을 잊지 말자!

다항법칙

다항법칙은 다항시간 복잡도가 동일한 다한 차수를 지닌 빅오 표기법을 지님을 나타낸다.

f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.

function a(n){
	let count = 0;
   	for (let i = 0;i < n*n; i++){
      // (1)
      count+=1;
    }
 	return count;
 }

위의 예에서는 1번에서 n*n 으로 f(n) = n^2 이므로 O(n) = n^2 이다.

제대로 이해했는지 점검하기

아래 코드들의 시간 복잡도를 직접 구해보며, 제대로 이해한건지 알아보자.

1번

function some(n){
  for(let i = 0; i < 1000*n; i++){
    for(let j = 0; j < 20*n; j++>){
    	console.log(i,j);
    }
  }
}

2번

function some(n){ for(let i = 0; i < 1000*n; i++){ for(let j = 0; j < 20*n; j++>){ for(let x = 0; j < n; j++>){ for(let y = 0; j < 20; j++>){ console.log(i,j); } } } } }

function some(n){
  for(let i = 0; i < 1000*n; i++){
    for(let j = 0; j < 20*n; j++>){
      for(let x = 0; j < n; j++>){
        for(let y = 0; j < 20; j++>){
        console.log(i,j);
        }
      }
    }
  }
}

3번

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

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

4번

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

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

정답
1. O(n^2)
2. O(n^3)
3. O(1)
4. O(log2 n)

요약

알고리즘을 풀때 복잡도를 계산하여 푸는 것은 굉장히 중요하다.
위의 법칙을 코드에 적용시켜 나의 코드가 대략적으로 복잡도를 어느정도 가지고 있는지 파악하며 더 나은 코드를 작성하기 위해 노력해야한다.