빅오표기법 Big-O

빅오표기법이란?

입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것

 

 

왜 사용할까?? 

예를 들어서 <1부터 N까지의 합을 구하는 함수를 구해보자>라고 했을 경우

 

예시 1)

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

예시 2)

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

이렇게 다양한 구현 방법이 나올 수 있다. 

 

이럴 경우 어떤 게 더 좋은 방법인지 기준이 명확하지 않다. 😮‍💨

각 각의 기기와 환경이 다르기 때문에 정확한 시간을 비교하기 쉽지 않았고

코드만 보고 판단하기 위해 빅오표기법을 사용하게 되었다. 

 

어떻게 사용할까?? 

연산 횟수가 다항식으로 표현될 경우,

최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타낸다.

 

예시)

n^2 + 2n +1의 성능을 가진 알고리즘이라면? 👉 O(n^2)

2n의 성능을 가진 알고리즘이라면? 👉 O(n)

 

 

즉, 최고차항이 가장 중요하다!!