빅오 표기법 (Big O notation)

빅오 표기법(Big O notation)은 알고리즘이나 함수의 시간 복잡도(time complexity)나 공간 복잡도(space complexity)를 표기하는 방법 중 하나입니다.

시간 복잡도란 입력 데이터 크기에 대해 알고리즘이나 함수가 동작하는데 걸리는 시간의 측정입니다. 이를 표기할 때 빅오 표기법은 최악의 경우를 가정하여, 알고리즘이나 함수의 시간 복잡도 상한을 표기합니다.

빅오 표기법의 핵심 포인트

1. Big O 표기가 왜필요한지를 알아야한다.
2. Big O 표기가 무엇인지 설명 해야한다.
3. 간단하게 Big O 표기를 표현하는방법
4. 시간복잡도와 공간복잡도를 이해한다.
5. 이를 토대로 알고리즘들을 평가한다.

빅오 표기법을 사용하는 가장큰 이유는 "시간의 문제" 때문입니다.
 - 디바이스(컴퓨터)마다 성능의 차이로 인해 시간차가 존재
 - 같은 디바이스에서도 성능을 측정할때 마다 다른 시간
 - 너무 빠른 알고리즘은 정확한 측정 불가능

이러한 경우들 때문에 빅오 표기법이 유용합니다.
빅오 표기법은 컴퓨터의 처리 시간으로 계산하지 않고 처리해야하는 연산 갯수로 비교하는 표기법 이기때문입니다.

Example 1. 1부터 N사이의 모든 숫자를 더하는 함수

의 두개의 코드는 1부터 N사이의 모든 숫자를 더하는 함수입니다. 두 함수의 코드는 다르지만 결과 값은 모두 같습니다.
그렇다면 어떤 코드가 더 좋은 코드라고 할수 있을까요?
위에서 말한 빅오 표기법으로 연산 갯수를 세어 어떤 코드가 더 좋은  코드인지 알아보도록 하겠습니다.

반응형

첫번째 코드의 경우에는 처음 total을 선언하는 연산자 1개를 제외하고 for문안에서 반복적으로 연산되는 연산자들의 개수는 5개 입니다. 그래서 5n+1 이 됩니다. O(5n+1)

두번째 코드는 n의 개수와 상관없이 총 3개의 연산자만 사용됩니다. O(3)

위의 두개의 코드는 비교적 짧기 때문에 연산자 개수를 세어볼 수 있지만 굉장히 연산자가 많은 코드라면 연산자 개수를 세는것만으로도 굉장히 힘들것 입니다.
빅오 표기법에서 핵심 개념은  코드의 전체적인 추세를 본다는것 입니다.
그렇기때문에 연산개수를 정확하게 세는 것은 중요하지 않습니다.
첫번째 코드의 5n+1은 결국 n이 되게 됩니다. 빅오 표기법으로 표시하자면 O(n)이 되게 됩니다.
두번째 코드의 O(3)은 결국 O(1)과 같은 성능을 낸다고 볼수 있습니다.

 

Example 2. 배열안에서 가장 큰수를 반환 하는 함수

function findMax(array) {
  let max = array[0];
  // array의 length만큼 시간이 증가하게 된다.
  for (let i = 1; i < array.length; i++) {
    if (array[i] > max) {
      max = array[i];
    }
  }
  return max;
}

코드는 n개의 원소를 가진 배열에서 최댓값을 찾는 함수입니다. 연산자 개수를 세어 본다면 O(5n+1)이겠지만 전체적인 추세를 봐야하기 때문에 위 코드의 시간 복잡도를 빅오 표기법으로 나타내면, O(n)입니다.