TIL 27. Big O Notation(빅 오 표기법)

Big - O

빅 오 표기법은 알고리즘의 성능을 수학적으로 표기하는 표기법이다. 이를 통해 시간 & 공간 복잡도를 예측할 수 있다. 오늘날 하드웨어의 성능이 매우 좋아짐에 따라 공간 복잡도가 알고리즘 성능에 미치는 영향이 점점 줄어들고 있어 빅오 표기법은 주로 시간 복잡도에 따른 성능을 예측하기 위해 사용되고 있다. 빅오 표기법으로 나타내는 시간복잡도는 알고리즘의 실제 러닝타임을 표기하기 보다 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는데 초점을 맞추고 있다.

알고리즘의 실제 러닝타임을 측정하는 것은 여러가지 한계가 있다. 먼저 기기 성능에 따라 같은 알고리즘이라도 러닝타임이 다르게 측정되기 때문에 서로 다른 알고리즘의 성능 비교가 어렵다. 또한 러닝타임이 매우 짧은 알고리즘들끼리 비교하는 경우 그 차이가 너무 미미해 측정이 어려울 수 있다. 이 때문에 빅오 표기법의 시간복잡도 계산은 러닝타임을 기준으로 하지 않고 인자값 n의 증가에 따라 작동 횟수의 증가율을 예측하는 방법을 사용한다.

(1) O(1), constant time

function (n) {
  return (n + n+1)/2
} 

숫자 n이 증가해도 작동 횟수는 동일하기 때문에 성능에 변함이 없다. 이러한 알고리즘을 O(1)의 시간 복잡도를 가지고 있다고 말한다.

(2) O(n), linear time

// n까지 정수의 총합을 구하는 알고리즘
function(n){ 
  let count = 0
  for (i =0; i<=n i++){
    count+=i
  }
 return count
}

위 알고리즘 n의 숫자가 늘어날 수록 for문이 동작하는 횟수도 비례하여 증가하는데 이처럼 O(n) 알고리즘 은 입력 데이터에 비례하여 처리 시간이 증가하거나 줄어드는 알고리즘을 말한다.

(3) O(n^2), quardratic time

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

위 알고리즘은 n개의 데이터를 받으면 각 데이터별로 n번씩 for문이 작동하는 이중 for문 형태로 n이 커질수록 n의 제곱만큼 처리시간이 증가한다. 이로 인해 O(n)보다 증가율이 크다.

(4) O(nm), quardratic time

founction(n,m){
  for (i=0; i<n; i++){
    for(j=0;j<m; j++){
      console.log(i+j)
    }
  }
}

n개의 데이터를 각각 m번씩 작동시키는 알고리즘으로 총 작동 횟수는 n과 m을 곱한 값이다. 이러한 알고리즘을 O(nm)알고리즘이라고 한다.

(5) O(n^3), polynomial / cubic time

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

위 알고리즘은 3중 for문 형태로 작동횟수는 n개의 데이터를 3번 곱한 횟수와 같다. O(n^3)알고리즘은 O(n^2)보다도 더 급격한 처리시간 증가율을 보인다.

(6) O(2^n), exponential time

O(2^n) 의 대표적인 알고리즘으로는 피보나치 수열이 있다.

function fibonacci(n){
  if (n < 2){
    retrun n
  }
  return fibonacci(n-1) + fibonacci(n-2)
}

매번 함수가 호출될 때마다 두번씩 호출이 되어 알고리즘 작동 횟수는 2^n번이 된다. O(n^3)이나 O(n^2)보다도 데이터의 증가에 따른 처리시간 증가율이 더 높다.

(7) O(log n)

O(log n)의 대표적인 알고리즘은 2진 검색이다. 2진 검색은 한번 실행 될 때마다 중간값 이전의 요소들을 날려버리기 때문에 순차검색에 비해 처리시간 증가율이 낮다. 따라서 O(n)에 비해 O(log n) 알고리즘의 처리 시간 증가율이 낮다. O(log n)알고리즘은 데이터가 증가해도 처리시간의 성능이 크게 달라지지 않는다.

상수는 버린다.

fuction (n){
  for(i=0; i<n; i++){
    console.log(n)
  }
  for(i=0; i<n; i++){
    console.log(n)
  }
}

위의 함수의 작동횟수는 2n번이지만 O표기법에서는 O(2n)이라고 표기하지 않고 O(n)이라고 표시한다. 빅 오 표기법은 실제 알고리즘의 러닝타임을 재기 위함이 아니라 증가하는 데이터 대비 처리시간의 증가율을 예측하기 위함이기 때문이다. 상수는 고정된 값이라 증가할 때마다 고정된 상수만큼만 영향을 미치기 때문에 빅 오 표기법에서 고려하지 않는다.