빅오 표기법 (Big O Notation) - 알고리즘 & 자료구조

Index

1. 빅오 표기법의 필요성
2. 빅오 표기법이란?
3. 빅오 표현식의 단순화하기
4. "시간 복잡도"와 "공간 복잡도"
5. 로그란?

1. 빅오 표기법의 필요성

코드가 그냥 동작하기만 해도 당장은 큰 문제점이 없다. 그러나 면접을 보거나, 코드 챌린지를 하거나 수천개 이상의 데이터를 다루는 프로젝트에서는 빠른 시간 내에 동작하는 것이 중요하다.

1부터 n까지 숫자를 모두 더하는 함수를 예로 들어보자.

첫 번째 방법은 1부터 n까지 for 루프를 돌려 total 변수에 하나씩 더한다.

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

두 번째 방법은 루프를 사용하지 않고 수학 공식을 사용한다.

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

둘 중 어떤 방법이 더 좋을까? 좋다는 기준으로는 더 빠른 것, 더 메모리를 적게 사용하는 것, 가독성이 좋은 것 등이 있다. 우리는 우선 속도에 초점을 맞춰서 생각해보자.

우리는 time function을 통해 타이밍을 측정할 수 있다. 자바스크립틑에서는 performance.now() 라는 메서드를 제공한다. 이를 통해 브라우저가 문서를 만든 시간과 문서가 열린 시간을 알 수 있다.

let openTime = performance.now();
addUpTo(100000000);
let closeTime = performance.now();
console.log(`Time Elapsed: ${(closeTime - openTime) / 1000} seconds.`)
// 1000분의 1초 단위이기 때문에 1000을 나눠주었다.

두 가지 방법에 대한 타이밍을 출력한 결과 두 번째 방법이 더 빠른 것을 확인할 수 있다.

이것이 가장 좋은 방법은 아니다. 우선 기기마다 다른 방식으로 시간을 기록하는 문제가 있다. 또한 같은 기기가 다른 시간으로 기록할 수 있다. 이런 단점은 여러 개발자와 협업하는 과정에서 번거로운 일로 작용할 수 있다. 마지막으로, 빠른 알고리즘에서는 순식간에 함수가 실행된다. 찰나의 순간의 속도를 측정하는 것은 정확하지 않을 수 있다.

그렇다면 시간을 측정하는 방법보다 더 좋은 방법은 어떤 걸까?

이렇게 시간을 측정하는 방법보다 더 좋은 코드 비교 방법이 바로 빅오이다.

코드가 실행될 때 걸리는 정확한 시간을 초 단위로 측정하는 것이 아닌 컴퓨터가 처리해야 하는 연산 개수를 비교하는 것이다.

두 번째 addUpTo 함수에서는 곱셈, 덧셈, 나눗셈 총 3번의 연산으로 이루어져 있다. 반면, 첫 번째 addUpTo 함수에서는 덧셈 하나만 있지만 루프를 돌기 때문에 총 n번 계산된다. 그러나 여기서 끝이 아니다. total += i는 total = total + i 이므로 대입 연산도 있다. 또한 for문의 i++도 i = i + 1 이기 때문에 2번 연산이 추가된다. 더 많은 연산이 있지만 우선 여기까지만 하도록...

우리는 이런 상세한 연산 갯수보다는 전체적인 추이를 보는 것이 더 중요하다. 핵심은 n이 증가할수록 연산 개수가 비례적으로 늘어난다는 것이다.

2 . 빅오 표기법이란?

빅오란 입력의 크기와 실행 시간의 관계를 말한다. 일반적으로 가장 높은 실행 시간 값들을 나타낸다.

예를 들어 두 번째addUpTo 함수는 연산이 총 3개이고 매개변수 값이 커진다 해도 연산 갯수에는 아무런 영향을 미치지 않는다. 실행 시간에도 변화가 없기 때문에 O(1)로 표기한다. 반면, 첫 번째 addUpTo 함수에서는 매개변수 값이 커질 수록 연산 갯수가 비례적으로 증가하므로 로 O(n)으로 표기한다.

여러 예시로 빅오 표기법에 대해 알아보자.

function countUpAndDown(n) {
  console.log("Going up!");
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
  console.log("At the top! Going down...");
  for (let j = n - 1; j >= 0; j--) {
    console.log(j);
  }
  console.log("Back down. Bye!");
}

첫 번째 for 루프에서 O(n)을, 두 번째 for 루프에서도 O(n)을 나타낸다. 그렇다면 두 가지 for 루프를 모두 가지고 있는 countUpAndDown 함수는 O(2n)이다. 하지만 n에 곱해진 숫자는 시간 복잡도에 큰 영향을 미치지 않으므로 생략할 수 있다. 따라서 시간 복잡도는 O(n)이라고 할 수 있다.

또 다른 예시를 보자.

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

두 가지 for 루프가 중첩되어 있다. 1차원 루프도 O(n), 2차원 루프도 O(n)이다. 1차원 루프에서 i가 하나씩 증가할 때마다 2차원 루프를 한 바퀴 돌아야 하기 때문에 시간 복잡도는 O(n²) 이라고 할 수 있다.

3. 빅오 표기식의 단순화하기

1. 산수는 상수이다.

2. 변수 배정도 상수이다.

3. 인덱스를 사용해 배열 요소에 접근하거나 키를 사용한 객체는 상수이다.

4. 루프에서, 복잡도는 루프의 길이에 루프 내부에서 일어나는 모든 일의 복잡도를 곱한 값이다.

몇 가지 예시를 통해 알아보자.

function logAtLeast5(n) {
  for (let i = 1; i <= Math.max(5, n); i++) {
    console.log(i);
  }
}

위 루프는 최소 5번, 최대 n번 순회한다. n은 5보다 훨씬 커질 수 있는 값이기 때문에 O(n)이라고 단순화할 수 있다.

function logAtMost5(n) {
  for (let i = 1; i <= Math.min(5, n); i++) {
    console.log(i);
  }
}

반면 루프가 최소 n번, 최대 5번 순회한다면 어떻게 될까? n은 5보다 큰 수 일 수도 있지만 순회는 최대 5번이기 때문에 O(1)이라고 단순화할 수 있다.

4. "시간 복잡도"와 "공간 복잡도"

우리는 시간 복잡도를 통해 알고리즘이 얼마나 빠르게 실행되는 지 알 수 있다. 우리는 지금까지 매개변수 값이 커질수록 알고리즘의 실행 속도가 어떻게 바뀌는 지 분석하였다. 이제부터는 값이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는 지 알 수 있는 공간 복잡도에 대해 알아보자.

자바스크립트에서 공간 복잡도

1. 대부분의 기본 요소(booleans, numbers, undefined, null)는 상수 공간이다.

2. 문자열은 O(n) 공간이 필요하다. (n: 문자열의 길이)

3. 레퍼런스 타입과 배열, 객체는 O(n) 공간이 필요하다.

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

sum 함수에서 공간을 차지하고 있는 부분은 total과 i 변수이다. 이 외에는 루프를 돌더라도 새로운 변수가 추가되는 일은 없다. 즉, 상수 공간인 O(1) 공간이 있다는 것이다.

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

double 함수에서는 루프가 돌 때마다 newArr 배열에 새로운 값이 추가된다. 새로 추가된 만큼 비례하여 공간을 차지하기 때문에 O(n) 공간을 차지하게 된다.

5. 로그란?

로그함수란 지수함수의 역함이다.

빅오에서 로그를 사용하면 O(n)과 O(n²)보다 적합한 O(log n)과 O(nlog n)을 표현할 수 있다는 점이다.

로그는 탐색 알고리즘과 효율적인 정렬 알고리즘, 그리고 재귀에서 주로 사용된다.

요약

• 알고리즘의 성능을 분석하기 위해서 빅오 표현법이 사용된다.

• 빅오 표현법은 알고리즘의 시간 및 공간 복잡도에 대한 이해를 높여준다.

• 빅오 표현법은 정확도가 아닌 전반적인 추세를 중요시한다.

• 빅오로 측정되는 시간 및 공간 복잡도는 하드웨어에 영향을 받지 않는다.