빅오 표기법

해솔·2023년 1월 5일

알고리즘

목록 보기

1/8

빅오 표기법(Big O Notation)

한 알고리즘 문제에는 여러가지 해결법이 존재한다. 그렇다면 해결법 중 가장 좋은 해결법은 무엇일까?
빅오 표기법은 여러가지 코드를 서로 비교하고 성능을 평가하는 방법이다. "좋은 코드 옆에 더 좋은 코드"가 아닌 숫자로(정량적으로) 코드 성능을 표기하고 분류할 수 있다.

아래는 1부터 n까지의 정수를 모두 합한 값을 반환하는 2가지 함수이다.

// 1번
function addUpToFirst(n) {
    let total = 0;
    for (let i = 1; i <= n; i++){
        total += 1;
    }
    return total;
}
// 2번
function addUpToSecond(n) {
    return n * (n + 1) / 2;
}

둘 중 더 좋은 코드는 무엇일까? 더 좋은 코드를 구분하는 기준은 무엇일까?

빠른 실행 속도?
메모리 공간 효율성?
쉽게 읽을 수 있는 코드?
짧은 코드?

이 중 빅오 표기법은 실행 속도(시간 복잡성) 와 공간 효율성(공간 복잡성) 을 측정한다.

시간 복잡성

코드의 실행 속도를 측정하기 위해 타이머 함수를 이용해 시간을 잴 수 있다.

let timer1 = performance.now();
addUpTo(1000000000);
let timer2 = performance.now();
console.log(`${(timer2 - timer1) / 1000} 초 걸림`)

타이머 함수를 이용해 시간을 재서 코드 성능을 분류하는 것은 문제가 있다.
기기 사양에 따라 두 함수의 실행 속도 차이가 달라질 수 있고 측정한 시간이 달라질 수 있다. 뿐만 아니라, 똑같은 기기에서 실행해도 매번 속도가 다르게 측정될 수 있고 매우 빠른 함수들을 비교할 땐 미세한 속도의 차이를 측정하기 힘들어진다.

그렇다면 별도의 타이머 코드를 쓰지 않고도 코드를 평가하는 더 좋은 방법이 있지 않을까?
빅오 표기법은 시간을 측정하는 대신 컴퓨터가 처리해야 하는 연산 개수를 카운트한다. 입력 값이 커질수록 알고리즘 실행 시간이 어떻게 변하는지(입력의 크기와 실행 시간의 관계를 전반적인 추세로 보는 것)를 설명하는 공식적인 방법이다.

f(n) = 1 => 상수 (n의 값이 커져도 실행 시간은 영향받지 않음)
f(n) = n => 선형 (n의 값이 커질수록 실행 시간도 비례해서 늘어남)
f(n) = n^2 => 이차 (n의 값이 커지면 실행 시간은 n의 제곱)

1번 함수의 경우, for 반복을 실행해 반복문 내의 연산은 n번 반복된다. 즉, n의 값이 커질수록 실행 시간도 늘어난다. 연산의 개수가 n의 곱과 연결되어 있고 빅오 표기법은 O(n)이다.
2번 함수의 경우, n의 값과 상관없이 연산의 개수는 항상 3개이다. 즉, n의 값이 커져도 실행 시간은 영향받지 않고 빅오 표기법은 O(1)이다.

// 1번
function countUpAndDown (n){
    console.log('카운트 시작')
    for (let i = 0; i < n; i++){ // O(n)
        console.log(i);
    }
    console.log('다시 내려감')
    for (let j = n - 1; j >= 0; j--){ // O(n)
        console.log(j)
    }
    console.log('카운트 끝')
}
// 2번
function printAllPairs(n) {
    for (let i = 0; i < n; i++){ // O(n)
        for (let j = 0; j < n; j++){ // O(n)
            console.log(i, j)
        }
    }
}

위의 두 함수는 모두 O(n)이 2개이다. 하지만 1번의 함수는 O(n)이 2개여도 O(2n)이 아닌 그냥 O(n)이지만 2번 함수는 O(n) 연산 안에 O(n)이 중첩되어 있으므로 O(n * n) = O(n^2)이다. 따라서 2번 함수는 n이 커지면 실행 시간이 n의 제곱으로 증가하게 된다.

아래의 경우들을 처리하는 시간은 값의 크기에 따라 다르지 않고 일정하다.

산술 연산
컴퓨터가 2+2를 처리하는 시간과 100만+2를 처리하는 시간은 큰 차이가 없다.
변수 할당
a = 20 과 a = 200만 의 처리 시간은 큰 차이가 없다.
인덱스를 사용해서 배열 요소에 접근하는 것 또는 키를 이용해 객체의 데이터에 접근하는 것

공간 복잡성

빅오 표기법에서의 공간 복잡성의 "공간"은 보조 공간을 뜻한다. 보조 공간은 입력된 값을 제외한 알고리즘 자체가 필요로 하는 공간을 말한다.

booleans, numbers, undefined, null은 입력값의 크기와 상관없이 모두 똑같은 공간 차지한다.

문자열은 O(n) 공간을 차지한다. (n = 문자열 길이)

참조 타입은 O(n) 공간을 차지한다. (n = 배열의 길이 또는 객체의 키 개수)

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

위 sum() 함수는 변수 total과 i에 각각 0이 할당된다. 0은 number type이므로 각각 O(1)이며 O(1 + 1)은 빅오 표기법에서 단순화하여 O(1)이다. 따라서 위 코드는 입력값의 크기와 상관없이 항상 차지하는 공간의 크기가 같다.

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

반면, double() 함수는 배열을 할당하므로 O(n) 공간을 차지한다.

빅오 표기법 단순화

빅오 표기법은 대략적인 큰 그림을 그리는 것이다. 1이든 500이든 그래프를 확대해서 보면 추세선의 차이가 크지 않다. 이러한 이유로 빅오 표기법을 단순화할 수 있다.

상수는 중요하지 않다.
O(500) = O(1)
O(2n) = O(n)
O(3n^2) = O(n^2)
작은 연산자도 중요하지 않다.
O(n + 10) = O(n)
O(1000n + 50) = O(n)
O(n^2 + 5n + 8) = O(n^2)

빅오 표기법을 단순화한 상태에서 속도나 공간을 비교하면 된다.

O(1) > O(n) > O(n^2) 순으로 속도가 빠르다.
O(1) > O(n) > O(n^2) 순으로 공간을 적게 차지한다.

로그(logarithm)

탐색 알고리즘과 효율적인 정렬 알고리즘은 로그 시간 복잡도와 관련이 있고 재귀는 로그 공간 복잡도와 관련이 있다. 로그를 표기법에 적용하면 아래의 순서로 속도나 공간을 비교할 수 있다.

O(1) > O(log n) > O(n) > O(nlog n) > O(n^2) 순으로 속도가 빠르다.
O(1) > O(log n) > O(n) > O(nlog n) > O(n^2) 순으로 공간을 적게 차지한다.

✍️ <JavaScript 알고리즘 & 자료구조 마스터클래스> 강의를 들으며 알게 된 내용을 정리하였습니다.

해솔

다음 포스트