Big O Notation(빅오 표기법)

Kingmo·2022년 8월 18일

Big O Notation(빅오 표기법)

1. 빅오 표기법이란?

코드를 분류하거나 비교할 수 있는 시스템

2. 어떻게 코드를 분류하거나 비교할 것인가?

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

console.log(addUpTo(100));

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

console.log(addUpTo(100));

둘 중 어느함수가 더 나은 함수인지 평가한다면
그 기준으로
속도, 적은 메모리 사용, 가독성을 생각할 수 있다.

그렇다면 이를 어떻게 평가할 것인가?

3. 코드 시간 재기

다음과 같은 방법으로 코드의 실행시간을 잴 수 있다.

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

let t1 = performance.now();
addUpTo(1000000000);
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`);
// Time Elapsed: 0.966 seconds.

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

let t1 = performance.now();
addUpTo(1000000000);
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`);
// Time Elapsed: 0.00009999999403953553 seconds.

로그에 찍힌 결과를 보면 두번째 함수의 실행시간이 더 짧은 것을 알 수있다.

허나 이 방법에는 문제점들이 있다.

이 방법의 문제점
- 코드를 실행할 때마다 콘솔에 찍히는 시간측정 결과가 다르다.
  기기사양, 무엇이 실행되고 있는지에 따라 측정결과가 다르게 나온다.
- 이렇게 수동으로 타이밍을 구하고 서로 비교하는 것은
  좋은 방법도 아니고 같이 논의 하기도 어렵다.
- 빠른 알고리즘은 정말 짧은 시간 안에 모든 것이 처리되기 때문에 이러한 방법으로 근소한 실행시간 차이를 측정할 수 없다.
때문에 코드를 비교할 때 시간을 비교하는 것은 문제가 있다.

4. 연산 갯수 세기

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

위 코드의 연산 갯수는 다음과 같이 셀 수 있다.

세 개의 연산 갯수를 찾을 수 있다.

그렇다면 다음과 같은 반복문에서는 어떻게 찾을 것인가?

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

위 코드의 연산 갯수는 다음과 같이 셀 수 있다.

n의 갯수에 따라 늘어나는 연산이 5개와 그렇지 않은 연산이 2개 있으므로
연산 갯수는 5n + 2 혹은 더 많을 수 있다.

여기서 5n + 2이던지, 3n 이던 50n이던지는 상관없다.
중요한 것은 큰 그림이다.
전체적인 추세를 보기만 하면 되기 때문이다.
위 경우에는 n이 커질 수록 연산의 갯수도 비례적으로 늘어난다는 것이 핵심이다.

빅오를 볼 때는 이런 것에 집중한다.

5. 시간 복잡도 시각화하기

n이 커질 수록 연산의 갯수가 비례적으로 늘어나는 함수의 경우

n에 1, 10, 100, 1000, 10000, 100000을 넣었을 경우
수가 커질 수록 다음과 같은 실행시간 변화를 가진다.

n의 값과 상관없이 항상 3개의 연산을 하는 함수의 경우

n에 1, 10, 100, 1000, 10000, 100000을 넣어도

위 처럼 동일한 퍼포먼스를 가진다.

이 처럼 시간 복잡도를 시각화하면
입력된 내용이 늘어날 수록 알고리즘 실행시간이 어떻게 변하는지 한눈에 볼 수 있다.

6. 빅오에 대한 공식 소개

위에서는 빅오 표기법이라는 용어를 사용하지 않고
빅오 개념들에 대해 이야기했다.

이제 제대로 빅오를 다루겠다.

빅오는 대략적으로 숫자를 세는 것에 붙인 공식적인 표현이다.

입력된 내용이 늘어날 수록 알고리즘 실행시간이 어떻게 변하는지 설명하는 공식적인 방식이다.

입력의 크기와 실행시간의 관계.

오로지 전반적인 추세에만 주목하는 것이 빅오이다.

빅오에서는
입력값이 얼마가 됐든 동일한 퍼포먼스를 보이면 O(1)이라 표기하고,
입력값과 퍼포먼스의 관계가 5n+2이던 5000n+2이던
궁극적으로 5n, 5000n은 n으로 단순화 할 수 있으니
이는 O(n)과 같이 표기한다.

아래와 같은 경우도 이중 배열이던, 삼중 배열이던 입력값을 끝없이 늘려 넣어
그래프를 만들면 13n^2이나 n^2이나 비슷하게 보이기 때문에
O(n^2)과 같이 표기한다.

n^2 + 5n + 8을 빅오로 표기한다면 O(n^2)으로 표기한다.
만약 n에 10억이 입력되었다고 하면 n^2에 비해 5n + 8이 갖는 크기는 미미하기 때문이다.

빅오에 적용되는 규칙

산수는 상수이다.
컴퓨터가 2+2를 처리하는 시간과 100만 + 2를 처리하는 시간은 비슷하다.

변수 할당도 상수이다.
x = 1000을 처리하던 x= 100만을 처리하던 비슷한 시간이 걸린다.

배열에 index나 객체에 key로 접근하는 것도 상수이다.

n개의 중첩 loop가 있다면 실행시간은 n^n이 된다.

아래 사진의 두 함수는 다음과 같이 빅오표기 할 수 있다.

logAtLeast5(n)함수는 최소 5번에서 n번의 반복문 실행,
logAtMost5(n)함수는 최소 n번에서 최대 5번의 반복문을 실행하기 때문에
상수만큼의 반복은 O(1)으로 나타낸다.

이 처럼 빅오 표기할 때는 반복의 최대치에 주목하는 것이 중요하다.

7. 공간 복잡도

위에서는 입력이 커질수록 알고리즘의 실행속도가 어떻게 바뀌는지 분석하였다.

이제는 입력이 커질수록 알고리즘이 얼마나 많은 공간(메모리)을 차지하는지에 대해 알아보자.

입력이 커진다는 것은 무한대까지 가면서 입력 자체가 커진다는 것이고,
여기서 주목할 것은 입력이아닌 알고리즘 자체가 필요로하는 공간이다.

공간 복잡도에 적용되는 규칙

boolean, 숫자, undefined, null은 자바스크립트에서 불변공간이기 때문에
모두 똑같은 공간을 자치한다.

문자열은 O(n)의 공간을 차지한다.
길이가 1자인 문자열보다 길이가 50자인 문자열이 50배많은 공간을 차지하기 때문이다.

참조타입은 n이 배열의 길이거나 객체의 키 갯수일 때 O(n)의 공간을 차지한다.

Example 1.

다음 함수를 보자.

위 함수는 입력의 크기와는 상관없이 변수 total과 i는 할당 받는 숫자가 바뀔 뿐이다.
여기서 숫자는 모두 똑같은 공간을 차지하기 때문에
이 함수의 공간 복잡도는 O(1)이다.
Example 2.

다음 함수를 보자.

double함수가 받는 인자배열이 길어질 수록
변수 newArr가 갖는 공간은 커진다.
때문에 이 함수의 공간복잡도는 O(n)이다.

8. 로그

어떠한 알고리즘들은 O(1), O(n), O(n^2)처럼 빅오가 간단하지 않은 경우가 있다.
이러한 경우 중 하나가 빅오가 O(log n)과 같은 경우이다.

빅오에서는 다음과 같이 로그의 밑이 어떤 수이건 log로 퉁쳐서 표현한다.
정확한 계산보다는 알고리즘의 퍼포먼스가 어떠한 그래프를 나타내는가가 중요하기 때문이다.

따라서 빅오에서는 다음과 같은 시간 복잡도 그래프를 보고

따라서 우리는 빅오에서 로그를 다룰 떄

O(n) 보다는 O(log n)이 더 낫고,
O(nlog n)은 O(n^2)보다 더 낫구나
n이 커질수록 O(n)에 비해 O(log n)은 시간이 별로 늘어나지 않는구나와 같이
O(nlog n), O(log n)이 갖는 성능의 정도만 파악할 줄 알면된다.