빅오 표기법과 시간, 공간 복잡도 알아보기

• Colt Steele 강사님의 알고리즘 강의를 듣고 TIL 방식으로 정리한 글입니다.

1에서 특정 n 까지의 값을 더하시오. 라고 문제가 주어지면 다음과 같이 작성할 수 있을겁니다.

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

console.log(addUpTo(6))
>> 21

또는 아래와 같이 작성할 수 있습니다. 핵심은 우선 어떻게 계산되는지에 초점을 두지 마시고, 성능에 대해 생각해봅시다.

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

console.log(addUpTo(6))
>> 21

과연 이 두 코드 중 어느것이 좋을까요? 좋은 것의 척도는 우선 다음과 같이 나눌 수 있을것 같네요.

1. 빠른가?
2. 메모리를 더 적게 사용하는가?
3. 더 쉽게 읽히는가?

여기서 대다수 사람들은 1, 2번을 답합니다. 지금은 속도를 우선으로 하겠습니다. 속도를 측정하는 가장 쉬운 방법은 내장 된 타이밍 펑션을 사용하는 것입니다.
이제 어떤 코드가 더 좋은 것인지 분석해 봅시다.
1번 코드

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.9882626670002937 seconds.

2번 코드

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.`)
>> 0.000010834001004695892 seconds.

2번 코드가 더 효율적인 것을 볼 수 있습니다. 다만 이런 척도로 어느것이 좋다 라는 것은 알맞지 않은 부분이기도 합니다.
언제나 다른 시간이 결과로 나올 것이며 정확하지 않습니다. 때문에 이런 측정은 도움이 되지 않습니다. 시간을 측정 하는 방법 외에 좋은 방법이 있는지 알아봅시다.

시간을 사용하지 않는 다면 무엇을 척도로 좋고 나쁜가를 판별할 수 있을까요? 이번에는 시간이 아닌 컴퓨터가 처리해야할 연산 갯수를 세보는 방식을 알아봅시다.
어떤 컴퓨터를 사용하든 연산 갯수는 변하지 않으니까요. 위에서 본 더 빠른 2번 코드를 살펴봅시다.

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

우선 연산자로 곱하기, 더하기, 나눗셈이 있습니다. 연산은 3번해야하는 것이죠. N이 어떤 값을 가지고 있든 3번의 연산이 이루어집니다. 이번엔 1번째 코드를 살펴봅시다

function addUpTo(n){
    let total = 0; // 1번 연산
    for(let i = 1; i <= n; i++){ // i = 1 -> 1번 연산, i <= n -> n번 연산 i++ -> n번 연산
        total += i; // +, = -> n번 연산
    }
    return total;
}

우선 더하기(+),그리고 대입(=) 연산자가 있습니다. 이곳에선 n의 갯수만큼 연산이 이루어집니다. 또한 for 루틴의 증가연산자도 있습니다. 전 코드에는 3개가 있다고 한다면 즉, 상수가 아니기 때문에 만일 n이 10인 경우 5n + 2 즉, 52번의 연산이 이루어집니다.
연산 횟수에 대해 후에 기술할 Big O 표기에 중요한 척도가 될 것입니다. 우선 참고해둡시다.

우선 function이 얼마나 오래걸리는지 시각정보를 보기 위해 다음 링크에 접속합니다. 해당 페이지는 이 강의의 강사분이 만드신 위젯입니다.
두 코드를 개별적으로 선택한 후 실행하면 전반적인 차이를 볼 수 있을것입니다.
우선 두 코드 모두 그래프의 형태는 선형으로 비슷할겁니다. 단, 실행시간에서 차이가 발생합니다.

Big O는 대략적으로 숫자를 세는 것의 붙인 공식적인 표현입니다. 정식으로 입력된 내용이 늘어날 수록 알고리즘 시간이 얼마나 걸리는지 표기한 것입니다. 입력의 크기, 실행시간의 관계를 말합니다.
위 링크에서 실행을 해보신 경우 1번째 코드는 시간이 N의 값이 늘어나는것과 비례하게 1:1 비율 즉 선형으로 늘어난 것을 볼 수 있습니다.

1. f(n) could be 선형 = (f(n) = n) : n이 커질 수록 실행시간도 커집니다.
2. f(n) could be 이차 = (f(n) = n²) : n이 커질 수록 실행시간이 n의 제곱
3. f(n) could be 상수 = (f(n) = 1) : n이 커져도 실행시간 상관없이 1 즉, 상수입니다.

이제 다시 한번 코드를 봅시다.
1번 코드의 실행시간은 n의 크기에 따라 실행시간도 1:1입니다. 즉 Big O 표기법으로, O(n) 입니다.

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

2번 코드의 실행시간은 Big O 표기법으로 상수. 즉, O(1) 입니다.

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

이제 O(n²)을 알아봅시다. 다음과 같은 경우를 예로 들 수 있습니다. 바로 중첩 루프입니다.

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

이 경우는 O(n)루프에 O(n)루프가 존재하므로 즉, O(n²)으로 표기합니다.
n이 커질수록 실행 시간이 n제곱의 값으로 늘어납니다. 이 경우 그래프로는 어떻게 나타날까요? 위의 링크에서 결과를 보면 지수 곡선을 그리는 것을 확인할 수 있습니다.

다음과 같은 경우가 있다고 봅시다 갯수에 상관없이 실행시간이 어덯게 나타날 것인가에 초점을 두고 오른쪽과 같은 표기법으로 표시합니다.

1. O(2n) -> O(n)
2. O(500) -> O(1)
3. O(13n²) -> O(n²)

결국 실행시간 그래프를 본다면 같은 모양을 그릴테니말이죠. 속도의 척도로 본다면 순서는 빠른 순 부터 다음과 같을겁니다.

1. O(1)
2. O(n)
3. O(n²)

또 다른 예시를 봅시다

1. O(n + 10) -> O(n)
2. O(1000n + 50) -> O(n)
3. O(n² + 5n + 8) -> O(n²)

코드에서 빅오를 판별하기 위한 조건을 알아봅시다

1. 산수(+, -, *, /)는 상수입니다.
2. 변수 배정도 상수입니다.
3. 인덱스를 사용해 배열 값에 접근. 혹은 객체에 값에 접근하기위해 키 찾기는 상수입니다.
4. 배열내 리스트 데이터를 루프로 접근한다면 n입니다. 만일 이차배열과 같은 루프의 중첩으로 리스트를 탐색한다면 n²입니다.

이제 코드를 봅시다.

function logAtLeast5(n){
    for (var i = 1; i<= Math.max(5, n); i++){
        // Math.max(인자, 인자) 인 경우 앞 인자가 크다면 앞 인자로, 아니라면 뒤 인자로 반환됩니다. 큰 값이 반환됩니다.
        console.log(i)
    }
}

n이 클 수록 연산 갯수가 n에 비례해 늘어나기(루프로 인해) 때문에 O(n)입니다.

또 다른 코드를 봅시다.

function logAtLeast5(n){
    for (var i = 1; i<= Math.min(5, n); i++){
        // Math.min(인자, 인자) 작은 값이 반환됩니다.
        console.log(i)
    }
}

이 경우 루프는 최대 5번까지만 반복되죠. 즉 n의 크기와는 상관이 없습니다. 적거나 5번까지만 반복될 뿐입니다. 이 경우 O(1)으로 표기합니다.
빅오 표기에 따라 시간 그래프의 모양은 아래와 같이 달라집니다.

입력 되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간 즉 공간 복잡도에 대해 알아봅시다. 시간 복잡도와는 별개로 보도록 합시다.

공간복잡도에는 규칙이 있습니다.

1. 우선 Boolean, number, undefined, null은 자바스크립트에서 불변 공간입니다. 입력(n)의 크기와 상관 없이 숫자가 1, 1000 이든 불변 공간입니다.
2. 문자열은 조금 다릅니다. 문자열은 O(n) 공간이 필요합니다. 'hello'의 경우 5의 공간을 차지합니다.
3. reference 타입, 배열, 객체도 같습니다. 대부분 O(n)으로 생각합니다. n은 배열의 갯수, 키의 갯수라고 볼 수 있습니다.

코드를 살펴보도록 합시다.

function sum(arr) {
    let total = 0; // one number O(1)
    for(let i = 0; i < arr.length; i++){ // i = 0 -> another nnumber O(1), 
        total += arr[i];
    }
    return total;
}

이제 공간에 집중해봅시다. 이 경우 공간 복잡도는 O(1)입니다.

또 다른 코드를 봅시다.

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

: double([1, 2, 3])
>> (3) [2, 4, 6]

배열의 크기가 커질 수록 공간도 newArr배열의 커집니다. 입력값에 비례해 공간도 늘어납니다. 즉 공간 복잡도는 O(n)입니다.

알고리즘 중 O(1), O(n), O(n²)처럼 빅오가 간단하지 않은 경우도 있습니다. 이 외에 log로 표현할 수 있습니다. log에 대해 정리해봅시다.

로그의 밑은 우선 숫자로 표기하겠습니다.
log2(8) = 3 -> 2의 몇 승이 8이 되나요? 3입니다.

로그함수와 지수함는 짝이라고 볼 수 있습니다.
log2(8) = 3 -> 2³ = 8

이후 글에서는 log === log밑2 으로 간주하여 표기하도록 하겠습니다.

이진 로그를 대략 계산하기 위해 숫자가 1보다 작아지기 전에 2로 나눠지는 횟수로 다음과 같이 정리할 수 있습니다.
25
12.5 /2
6.25 /2
3.125 /2
1.5625 /2
0.78125 /2

log(25) 4.64

아래 그림을 다시 봅시다. 대략적으로 O(log n)은 O(n)보다 좋고, O(nlog n)은 O(n)보다 좋지 않습니다. 여기까지만 알아두고 진행해봅시다.

자 이제 로그를 어디에 사용할 수 있을까요? 정렬 알고리즘, 재귀, 탐색 알고리즘 등에서 마주할 수 있을 겁니다. 우선 그래프를 대략적으로 어떤 것이 더 좋은지 기억해두도록 합시다.