빅오표기법 (Bio O notation)

출처: https://unsplash.com/ko/%EC%82%AC%EC%A7%84/KvX6DQsOKrc

해당 글은 Udemy "JavaScript 알고리즘 & 자료구조 마스터 클래스" 수업을 기반으로 작성한 내용입니다.

Bio O notation 이란?

문제를 해결하기 위해 작성된 코드들을 서로 비교하고 해당 코드의 성능을 평가하기 위해 사용하는 방법이다

좀 더 쉽게말하면, 코드 성능에 대해 해당 코드들을 분류하고 서로 비교하여 수치로 환산할 수 있는 표기법이다

 

왜 필요할까? 꼭 써야할까?

성능적인 측면에서!
면접을 보거나, 코드 챌린지를 하거나, 수백만 수천만개의 데이터셋을 다루는 경우, 어떤 알고리즘이 다른 알고리즘에 비해 실행하는게 걸리는 시간이 한 시간이 더 빠르다면? 매우 중요하다!  performance matters!

 

의사소통 측면에서!
코드의 성능을 이야기 하는데 있어서 정확한 전문용어(precise vocabulary, terminology)를 사용하는것이 서로에게 정확한 의사소통의 기준이 될 수 있다

 

그 외...

하나의 알고리즘이 다른 알고리즘에 비해 모든 면에서 뛰어나고 다른 알고리즘은 엉망인 경우는 드물다 각 알고리즘마다 장단을 가지고 있다 빅오 표기법을 통해 이러한 장단점에 대해  명확하게 비교할 수 있다

 

비효율적인 코드를 디버깅하는데 도움이 된다(추가 조사 필요)❗️

 

기술 면접에 많이 나온다(ㅋㅋ…)

 

시간복잡도 (Time Complexity)

보통 빅오표기법은 구체적이고 정확한 수치보다는 큰 그림을 바라보듯이 전체적인 맥락에서 이해하는 것이 중요하다

빅오표기법을 통해 특정 코드에 대한 시간복잡도에 대해 이야기하는 경우, 해당 코드를 실행했을때 걸리는 시간의 최대치를 말한다(구체적인 시간이 아니다)

다시말하면, 코드를 실행시켰을때 가장 오래걸리는(worst) 경우를 가정한다

 

예를들어보자

아래의 코드에서

1번의 경우, addUpTo 함수에서는 대략적으로 5n + 2번의 연산이 이루어지고

2번의 addUpTo 함수에서의 연산은 총 3번 이루어진다!

//#1 
function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

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

여기에서 1번의 경우,

n앞의 숫자 5는 중요하지 않다!(전체적 맥락을 이해해야한다는 말의 의미)

 

왜냐하면 빅오 표기법을 통한 시간복잡도는 n의 개수가 증가하면서 걸리는 시간의 증가 추이를 알아보는 것이기 때문에 연산이 100번 일어나든 100000번 일어나든 시간복잡도에는 큰 영향을 주지 않는다.

 

중요한것은 1번의 경우 n의 개수가 증가하면 그에 비례하여 연산의 시간도 일정하게 증가한다는 것이고(O(n)의 시간복잡도를 갖는다),

2번의 경우에는 n의 개수가 증가할 때 연산을 하는 시간은 증가하지 않고 일정하다는 것이다(O(1)의 시간복잡도를 갖는다)

 

기본적으로 for 문과 같은 반복문은 O(n)의 시간복잡도를 갖는다

즉, n의 수의 비례해서 코드 연산 처리 시간도 일정하게 증가하며 이를 선형(linear)의 시간 복잡도라한다

 

아래 3번의 경우에는,

//#3
function printAllPairs(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
}

 

중첩 반복문을 사용하기때문에 O(n²)의 시간 복잡도를 갖는다

O(n²)의 시간 복잡도란 n이 커질수록 코드 연산 처리 시간이 n 제곱 값으로 늘어난다는 의미이며 기하급수적 시간복잡도 (exponential time complexity)라 한다.

 

Bio O notation 단순화하기

빅오 표기법을 거시적인 관점에서 보면 다음과 같은 결론을 내릴 수 있다.

 

상수는 중요하지 않다 (Constants don’t Matter)

O(2n)❌         O(n)✅

연산의 개수가 n이 증가함에 따라 일정하게 증가한다는 뜻
n이 증가하면서 처리해야할 연산의 개수가 일정하게 증가하므로 연산 처리에 필요한 시간도 일정하게 증가!

O(500)❌         O(1)✅

연산의 개수가 어떤 상황에서든 500개라는 뜻
n이 몇개든지 상관없이 연산을 500번만 하면 된다는 말이므로 어떤 경우에서든지 걸리는 시간은 동일!

O(13n²)❌         O(n²)✅

이 경우에는 상수(숫자 13)는 크게 상관없음
상수가 아무리 클지라도 전체적인 맥락(그래프를 무한히 확장, 그래프를 우주에서 본다고 생각ㅎㅎ)에서 큰 차이를 보이지 않음
n이 증가하면서 걸리는 시간은 제곱으로 증가!

 

더 작은 단위는 중요하지 않다(Smaller Terms don’t Matter)

O(n + 10)❌			O(n)✅
뒤에 있는 숫자 10은 중요하지 않다

O(1000n + 50)❌			O(n)✅
위에서 설명한 것과 마찬가지로 n 앞에 있는 상수 1000은 중요하지 않다
50 또한 시간복잡도를 산출해 내는데 큰 영향을 주지 않는다

O(n² + 5n + 10)❌		O(n²)✅
n²의 입장에서는 5n, 10은 중요하지 않다

 

Big O Shorthands

숫자 크기에 상관없이 산수 연산 처리에 걸리는 시간은 일정하다 (Arithmetic operation are constant)

2 + 2 
2 + 1000000 

연산하는데 걸리는 시간은 동일!

변수에 값을 할당하는데 걸리는 시간 비슷하다 (Variable assignment is constant)

const x = 2;
const x = 10000;

변수에 할당하는 숫자의 크기에 상관없이 할당하는데 소요되는 처리 속도는 동일

 

 

또한, 배열에서 첫번째 요소를 찾든 100번째 요소를 찾든 인덱스를 사용하면 동일한 시간이 소요된다

 

객체에서도 마찬가지로 key를 이용해 value에 접근하는 시간도 일정하다

 

위에서 말한 내용을 적용해 본 예시는 다음과 같다

function logAtLeast5(n) {
  for (let i = 0; i <= Math.max(5, n); i++) {
    console.log(i);
  }
}
//시간복잡도 O(n)
//n이 커질수록 연산의 개수가 n에 비례하여 증가


function logAtMost5(n) {
  for (let i = 0; i <= Math.min(5, n); i++) {
    console.log(i);
  }
}
//시간복잡도 O(1)
//n의 크기와 상관없이 연산의 개수 동일

 

공간 복잡도 (Space Complexity)

공간복잡도에서의 공간이란 알고리즘에서 일어나는 공간, 보조 공간 복잡도(auxiliary space complexity)를 말한다

 

대부분의 원시 자료형(string, booleans, numbers, undefined, null 등)은 일정한 공간 복잡도를 갖는다(불변의 공간이기 때문에)

 

예를들어,

문자열(string)의 경우 문자의 길이가 n이라면 O(n) 공간 복잡도를 갖는다

어떤 문자열의 길이가 50인 경우 길이가 1인 문자열보다 50배 더 많은 공간을 차지하게 된다

 

참조 자료형인 경우 일반적으로 O(n)의 공간복잡도를 갖는다 (배열의 경우 length가 n 인 경우, 객체의 경우 key의 개수가 n인 경우)

 

예를들어, 어떤 배열의 길이가 4이고 또 다른 하나가 2라면 길이가 긴 배열이 짧은 배열보다 2배 더 많은 공간을 차지하게 된다

 

아래의 코드의 경우, 변수 total, i에 각 숫자를 할당하기때문에 총 2개의 space가 생기며 인자로 들어오는 배열 arr의 크기에 상관없이 공간 복잡도는 일정하기때문에 O(1)이라고 할 수 있다.

function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]; //재할당은 고려하지않는다
  }
  return total;
}

 

아래의 경우,

double 함수의 인자로 입력된 arr의 길이에 비례해서 newArr의 길이가 증가한다

따라서 해당 코드의 공간복잡도는 O(n)이라 할 수 있다

function double(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(2 * arr[i]);
  }
  return newArr;
}

 

로그 Logarithm

지수 함수의 역함수(지수함수 n²)이며,

로그함수와 지수함수는 짝의 관계 이다

아래 그림과 같이, 빅오 표기법에서는 log의 base number를 삭제하고 표기한다 

요약 Recap

• 알고리즘의 성능(시간, 공간)을 분석하기 위해 빅오표기법 사용
• 입력의 크기가 늘어날 수록 전체적인 추이를 바라본다(general trend, 상당히 큰 경우)
• 빅오 표기법은 정확한 것보다는 전반적인 추이에 대해 생각해보는 것이다
• 빅오표기법을 통해 시간 및 공간 복잡도에 대한 이해를 높일 수 있다
• 빅오표기법으로 측정되는 알고리즘의 시간 및 공간복잡도는 하드웨어의 영향을 받지 않는다