들어가며

앞서 작성한 알고리즘 글에서 '시간 복잡도는 ~입니다.'라는 말을 여러번 했는데요, 이 말을 이해하기 위해서는 빅오(BigO)라는 개념에 대해서 알아야합니다.

오늘은 알고리즘을 공부한다면 빼놓을수 없는 빅오(BigO)가 도데체 무엇인지 알아보겠습니다😎.

빅오 (Big O)

빅오의 정의

빅오(Big O)는 코드를 분류하거나 비교할 수 있는 시스템으로, 숫자로 코드의 성능을 표기합니다. 다시말해, 빅오는 알고리즘의 성능을 분석하기 위해서 사용하는 표기법입니다.

빅오는 코드의 성능을 무엇으로 나누냐에 따라 시간 복잡도와 공간 복잡도로 나눌 수 있습니다.

시간 복잡도 (Time Complexity)는 입력값에 따른 알고리즘의 실행 속도가 어떻게 변하는지를 나타냅니다.
공간 복잡도 (Space Complexity)는 입력값에 따라 알고리즘이 얼만큼의 공간(메모리)을 차지하는지 나타냅니다.

두 복잡도는 정확도가 아닌 전반적인 추세를 나타내며, 일반적으로 가장 높은/큰(최대치) 실행시간/메모리를 나타냅니다. 또한, 두 복잡도는 하드웨어의 영향을 받지 않습니다. 이 말은, 저의 컴퓨터에서 실행한 함수의 복잡도와 슈퍼컴퓨터에서 실행한 함수의 실행 속도는 다를 수 있지만 복잡도는 동일하다는 뜻입니다.

빅오의 필요성

그렇다면 빅오는 무슨 이유로 필요한걸까요?

문자열을 받아 뒤집어 출력하는 함수를 만들어야 한다고 생각해봅시다. 이러한 함수를 만드는 방법을 스택오버 플로우에 검색해보면 정말 여러가지 방법을 찾아볼 수 있습니다. 그러면 이 많은 선택지 중 어떤 방법을 사용하는 것이 가장 좋을까요?

위와 같은 질문을 했을때 '음... 1번 함수가 가장 빠르게 실행되고, 2번 함수는 그저 그래. 3번 함수는 너무 느려!' 등과 같이 애매모호하게 설명할 수 밖에 없다면 함수 사이의 성능 차이를 구분하기 어렵겠죠. 빅오는 이런 문제를 해결해줍니다. '1번 함수의 빅오는 ~이기 때문에 3개의 함수 중 시간복잡도가 가장 좋아.'라고 명확하게 설명할 수 있는 것이죠.

빅오의 성능 측정

빅오는 숫자로 코드의 성능을 표기한다고 했습니다. 여기서 말하는 코드의 성능이란, 코드가 실행되는데 걸리는 절대적 시간 혹은 코드가 사용하는 절대적 메모리 양이 아니라, 코드를 실행하기 위해 컴퓨터가 처리해야하는 연산 갯수의 추세를 의미합니다.

(시간으로 코드의 성능을 체크해 볼 수 있겠지만, 코드가 실행되는 환경과 상황에 따라 시간은 모두 다르게 나타날 수 있기 때문에 이는 일정하게 확인하기 어렵습니다.)

실제 함수를 통해 빅오를 어떻게 나타낼 수 있는지 확인해 봅시다. 아래 두 함수는 n을 입력값으로 주면 1+2...+n 처럼 1부터 n까지 모든 숫자를 더해 반환하는 함수입니다.

첫번째 addUpTo함수를 봅시다. n에 어떤 값이 들어와도 곱하기(*), 더하기(+), 나누기(/) 총 3번의 연산이 이루어집니다. 즉, n의 값과 상관없이 연산의 횟수가 일정하면 빅오 표기법으로 O(1)라고 나타냅니다(시간 복잡도).

const addUpTo = (n) => {
  return (n * (n + 1)) / 2
}

두번째 addUpTo함수는 for문을 사용했습니다. 이를통해 n의 값 비례해 연산의 횟수가 늘어난 다는 사실을 알 수 있습니다. 예를들어, total += i의 + 연산이 있는데 이는 n의 값의 횟수만큼 연산이 실행될 것을 알려줍니다. 따라서 이 함수는 빅오 표기법 O(n)으로 나타낼수 있습니다(시간 복잡도).

const addUpTo = (n) => {
  let total = 0
  for (let i = 1; i <= n; i++) {
    total += i
  }
  return total
}

빅오의 표기법

빅오는 코드를 실행하기 위해 컴퓨터가 처리해야하는 연산의 추세를 나타낸다고 했습니다. 연산의 정확한 갯수가 아니라 연산의 대략적인 추세를 알고자 하는 것입니다. (강조..!)

따라서 빅오는 아래의 예의 왼쪽처럼 자세한 수를 나타내지 않고 이에 오른쪽과 같이 추세만은 표기하여 사용합니다.

O(2n) -> O(n)
O(500) -> O(1)
O(13n2) -> O(n2)

빅오를 그래프로 나타내면 다음과 같습니다.

빅오 공간 복잡도

공간 복잡도는 입력값에 따라 알고리즘이 얼만큼의 공간(메모리)을 차지하는지 나타내는 것이라고 했는데요, 공간 복잡도를 알기 위해서는 아래의 특성을 알고있어야 합니다.

boolean, numbers, undeined, null은 O(1)의 공간을 차지합니다.
string, 배열, 객체는 O(n)의 공간을 차지합니다.

아래 sum함수의 공간복잡도를 예상해 봅시다. let total = 0;에서 변수 total에 숫자를 담고 있으며, let i = 0;에서도 마찬가지로 변수 i에 숫자를 담고 있습니다. for문 안에서는 기존에 이미 공간을 차지하고 있는 total이라는 변수에 값을 더할 뿐 새로운 공간을 생성하지는 않습니다. 매개변수 arr의 크기와는 상관없이 필요한 메모리 공간은 2개로 항상 같습니다. 그러므로 sum함수의 공간복잡도는 O(1)입니다.

const sum = (arr) => {
  let total = 0
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]
  }
  return total
}

하나 더, 아래의 double함수의 공간 복잡도도 확인해 봅시다. 매개변수 arr의 길이에 따라 newArr에 새로운 값을 담아 반환합니다. 즉, arr의 배열의 길이가 n이면 newArr에도 n개의 요소가 저장되어 반환되겠죠. 그러므로, double함수의 공간복잡도는 O(n)입니다.

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

함수 별 시간/공간 복잡도

같은 함수라고해도 시간 복잡도와 공간 복잡도는 일치하지 않을 수 있습니다. 각 함수 별로 시간 복잡도와 공간 복잡도를 확인해 봅시다. 하나 하나 설명을 적어놓지는 않았지만 왜 이 함수가 이런 시간 복잡도와 공간 복잡도를 갖는지 생각해 보면 좋을 것 같습니다.

시간복잡도 : O(n) / 공간복잡도 : O(1)

function logUpTo(n) {
  for (var i = 1; i <= n; i++) {
    console.log(i)
  }
}

시간복잡도 : O(n) / 공간복잡도 : O(1)

function logAtLeast10(n) {
  for (var i = 1; i <= Math.max(n, 10); i++) {
    console.log(i)
  }
}

시간복잡도 : O(1) / 공간복잡도 : O(1)

function logAtMost10(n) {
  for (var i = 1; i <= Math.min(n, 10); i++) {
    console.log(i)
  }
}

시간복잡도 : O(n) / 공간복잡도 : O(n)

function onlyElementsAtEvenIndex(array) {
  var newArray = Array(Math.ceil(array.length / 2))
  for (var i = 0; i < array.length; i++) {
    if (i % 2 === 0) {
      newArray[i / 2] = array[i]
    }
  }
  return newArray
}

시간복잡도 : O(n2) / 공간복잡도 : O(n)

function subtotals(array) {
  var subtotalArray = Array(array.length)
  for (var i = 0; i < array.length; i++) {
    var subtotal = 0
    for (var j = 0; j <= i; j++) {
      subtotal += array[j]
    }
    subtotalArray[i] = subtotal
  }
  return subtotalArray
}

빅오의 관점에서 보는 객체/배열/내장 메소드

객체

객체는 정렬할 필요가 없는 데이터이며, 데이터에 빠르게 접근 가능하고, 데이터를 삽입/제거 또한 빠르게 할 수 있습니다. 여기서 '빠르다'라는 의미는 빅오가 상수 시간 O(1)이라는 뜻입니다. 탐색은 조금 다른데요, 객체의 데이터 탐색은 key에 접근하는 것이 아니라 그 값이 무엇인지까지 확인해야 합니다. 즉, N이 늘어늘 수록 걸리는 시간도 늘어난다는 의미이며 객체 탐색의 빅오는 선형 시간 O(n)입니다.

객체의 빅오를 정리하자면 다음과 같습니다.

삽입 : O(1)
제거 : O(1)
접근 : O(1)
탐색 : O(n)

객체의 메소드들의 빅오도 살펴봅시다.

Object.keys, Object.values는 객체의 key/values를 배열에 담아 반환해 줍니다. 즉, 객체의 요소 N이 늘어날 수록 반환해야 하는 요소도 늘어나게 되므로 빅오는 O(n)입니다.
Object.entries는 위 두 메소드에 비해 key-value를 모두 반환해줘야해서 작업이 조금 더 많은 듯 하지만 빅오는 추세를 나타내는 것이기 때문에 빅오는 역시나 O(n)입니다.
hasOwnProperty는 속성이 존재하는지를 boolean값으로 반환해주는 메소드입니다. 즉, 객체의 탐색 후 그 값을 boolean으로 반환해주므로 빅오는 O(1)입니다.

객체의 메소드들의 빅오를 정리하지면 다음과 같습니다.

Object.keys : O(n)
Object.values : O(n)
Object.entries : O(n)
hasOwnProperty : O(1)

배열

배열은 데이터를 정렬해야하는 경우 사용합니다. 물론, 정렬이 필요하지 않은 경우에도 배열을 사용할 수 있지만 데이터를 삽입/제거하는 경우 성능을 희생 해야할 수도 있습니다.

배열에서 데이터를 삽입/제거하는 것은 경우에 따라 다른 빅오를 갖습니다. 배열의 마지막 요소에 데이터를 삽입/제거하는것은 빅오 O(1)이지만, 배열의 첫 요소에 데이터를 삽입/제거하게되면 기존 요소들이 가지고있는 인덱스를 모두 바꿔줘야하기 때문에 빅오가 O(n)이 됩니다. 즉, 빈배열일 경우를 제외하고 push/pop이 shift/unshift 작업보다 빠르다는 것을 알 수 있습니다. 데이터 접근의 경우에는 상수 시간 O(1)의 빅오를 갖는데요, 이유는 배열에는 요소마다 인덱스 값을 가지고 있기 때문에 10번 인덱스에 접근하고자 하면, 0부터 10까지 하나씩 찾아보는것이 아니라 바로 10번 인덱스로 접근 할 수 있기 때문입니다.

배열의 빅오를 정리하자면 다음과 같습니다.

삽입 : 배열 마지막 부분에 삽입하면 O(1) / 배열 첫 부분에 삽입하면 O(n)
제거 : 배열 마지막 요소를 제거하면 O(1) / 배열 첫 요소를 제거하면 O(n)
접근 : O(1)
탐색 : O(n)

배열의 메소드들의 빅오도 알아봅시다.

push : O(1)
pop : O(1)
shift : O(n)
unshift : O(n)
concat : O(n)
slice : O(n)
splice : O(n)
sort : O(n * logn) -> 정렬은 O(n)보다는 크다는 사실을 인지!
forEach/map/filter/reduce/etc. : O(n)

참고) 로그(Log)란?

중간 중간 로그(log)를 발견하셨을 텐데요, 로그는 중학교(?)에 다닐때 배웠던 것으로 기억이 납니다.로그를 보고 당황했다면, 아래와 같은 규칙을 가지고 있다는 사실 정도만 알아둡시다.

참고로 O(log n)시간복잡도는 시간 복잡도가 낮고, O(nlog n)은 시간 복잡도가 높습니다. 즉, 알고리즘의 시간 성능을 높이고 싶다면 O(nlog n)의 시간 복잡도를 가진 함수보다는 O(log n)를 선택하는 것이 좋겠죠?

맺으며

오늘은 빅오가 무엇인지, 빅오의 시간복잡도와 공간복잡도 그리고 객체/배열의 빅오에 대해서 알아보았습니다. 빅오를 알고나니 앞으로 함수 혹은 객체/배열을 사용할 때 시간복잡도와 공간복잡도가 무엇일지 생각하면서 코드를 작성할 수 있겠다는 생각이 듭니다. 알고리즘은 알아갈수록 흥미롭네요🤓!

참고

JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 듣고 스스로 정리하여 작성한 글 입니다.

빅오(BigO)에 대해서 알아보자