빅오(Big O) 표기법이 뭘까? 어떻게 보는 거지?

빅오(Big O) 표기법이 뭘까? 어떻게 보는 거지?

📖 들어가며

알고리즘, 자료구조를 공부하는 데에 있어서 자꾸 빅오(Big O), 빅오(Big O) 거리는데 도대체 빅오(Big O)가 뭐고 왜 사용하는 건지 몰라서 공부한 내용을 정리하게 된다.

1. 빅오(Big O) 표기법은 왜 사용하는 거지?

먼저 빅오(Big O) 표기법을 왜 사용하는 걸까.

자료구조, 알고리즘 해결에 있어서 문제를 해결할 수 있는 방법이 여러 가지인 경우가 대다수이다.

정수 n을 받으면 1부터 n까지의 합을 구하는 두 가지의 코드를 예로 들어보겠다.

첫 번째 코드

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

두 번째 코드

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

첫 번째 코드는 반복문을 이용해서 1부터 n까지의 숫자를 더해서 구하는 방법이고,

두 번째 코드는 수학적인 공식을 이용해서 1부터 n까지 숫자의 합을 구하는 방법이다.

두 코드의 결과는 같게 나온다.

하지만 어떤 방법이 더 좋고 더 나은 방법인지 알 수 없다.

그래서 이것을 판별하기 위해서 빅오(Big O) 표기법을 사용한다.

이렇게 일반적으로 서로 비교하고 성능을 평가하고 비교할 수 있는 목적을 가지고 있는 것이 빅오(Big O) 표기법이라고 한다.

"좋은 코드", "나쁜 코드", "그냥저냥인 코드"를 숫자로 코드의 성능을 표기할 수 있는 것이다.

반응형

2. 그래서 빅오(Big O)는?

즉, 입력값과 연산 수행 시간에서 상관관계를 나타내는 척도를 시간 복잡도라고 하고 이를 빅오(Big O) 표기법으로 표기한다. 물론 공간 복잡도에 대해서도 사용될 수 있다.

입력된 값이 커질수록 알고리즘 실행시간이 어떻게 변하는지 설명하는 공식적인 방법.

시간 복잡도, 공간 복잡도를 쉽게 볼 수 있게 표기하는 대표적인 방법 빅오(Big O)다.

3. 빅오(Big O) 표기법은 어떻게 표기할 수 있는 걸까?

보통 사용하는 표기법으로는

O(1), O(log n), O(n), O(n^2), O(n log n), O(2^n) 등등 있다.

그럼 이 표기법은 어떻게 알고 표기를 하는 것일까.

몇 가지 예를 들면서 알아보자.

3-1 O(1)

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

입력값 n이 커질수록 약간의 변동을 있을 수 있지만 전반적인 주제에는 변화가 없다.

10으로 계산하던지 10000으로 계산하던지 연산하는 수(코드에서의 곱셉, 덧셈, 나눗셈)는 변하지 않기 때문에

O(1)로 표기한다.

3-2 O(n)

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

반복문을 사용하기 때문에 입력값 n이 커질수록 연산을 하는 횟수는 n의 크기에 따라서 변하게 된다.

반복문에서 보면 i와 n을 비교하고, i를 증가시키고, 변수 total에 더해주고 하고 있는데,

n이 10이면 이 연산들을 10번 더 반복하게 되는 것이고 10,000번이면 이 연산들을 10,000번 더 반복하게 된다.

n의 크기에 따라서 시간이 달라지게 되기 때문에 O(n)으로 표기한다.

 

빅오(Big O)는 디테일한 것은 신경 쓰지 않고 광범위한 부분만 보면 된다.

즉, 광범위한 추세만 보기에는 상수는 전혀 중요하지 않기 때문에 O(10n) => O(n), O(300) => O(1), O(5n^2) => O(n^2) 등 이런 식으로 표기하는 것이다.

3-3 계산 방법

간단하게 말하면 연산이 몇 번 수행되는지, 입력 값과 연산의 관계가 어떻게 되는지 보면 쉽게 알 수 있다.

4. 빅오(Big O) 표기법의 종류는?

O(1): 입력값이 크기에 많은 차이가 있어도 일정한 실행시간을 보여주는 최고의 알고리즘이라고 할 수 있다.

O(log n): 로그는 입력값이 매우 커도 크게 영향을 받지 않는 알고리즘에 해당된다.

O(n): 입력값과 알고리즘 수행시간이 비례한다.

O(n log n): 병합 정렬 같은 효율이 좋은 알고리즘이 대부분 이에 해당된다.

O(n^2): 중첩, 버블 정렬 같은 비 효율적인 알고리즘이다.

O(2^n): 피보나치의 수를 재귀함수로 계산하는 알고리즘에 해당된다.

O(n!): 매우 느리고 입력값이 작아도 계산 속도가 매우 증가한다.

입력 N값에 따른 알고리즘 시간 복잡도

n값에 따른 알고리즘 시간 복잡도 표 (출처: https://blog.chulgil.me/algorithm/)

 

빅오(Big O) 성능 시각화 자료

📕마치며

빅오(Big O) 표기법이 무엇인지, 어떻게 표기하는 건지 등 배운 내용을 간단하게 정리해 봤다.