[알고리즘]Big O Notation

알고리즘 성능 평가

어떤 알고리즘이 있을 때, 그 알고리즘의 성능 평가는 어떻게 할 수 있을까?

알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다.

시간 복잡도와 공간 복잡도가 있으며 복잡도가 낮을수록 좋은 알고리즘이다.

시간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석
공간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석

 

이 개념들을 왜 알아야 할까?

1. 작성한 코드가 어떻게 동작하는지에 대해 정확한 전문 용어를 사용하는 것은 중요하다.
2. 서로 다른 접근 방식 간의 균형에 대해 논의하는 데 유용하다. 예를 들어, 한 해결책이 정말 좋고 다른 하나는 엉망인 경우가 많지 않다. 어떤 건 많은 데이터양을 다루는 것에 유용하고, 다른 하나는 더 오래 걸려도 처리하는 시간의 변동이 적을 수 있다. 여러 접근 법의 장단점을 얘기할 때 이 개념들이 도움이 된다.
3. 코드가 충돌하거나 속도가 늦춰질 때, 에러를 잡는 것 만이 아니라 비효율적인 코드를 식별하면 애플리케이션의 문제점을 찾는 도움이 된다.

JS 코드로 예시를 보자.

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

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

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

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

위 두 코드는 같은 결과를 가져온다. 어느 코드가 더 나을까? 

"더 나은 것"은 무엇을 의미하나?

• 더 빠른 것?
• 메모리를 얼마나 사용하는지?
• 가독성이 좋은지?

세 가지 다 따져봐야 할 문제이지만 속도 측면에서 살펴보자. 위 코드를 수동으로 타이밍을 구하고 비교해보자.

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

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

실행 결과

 

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

const time1 = performance.now();
addUpTo(1000000000);
const time2 = performance.now();
console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`)

실행 결과

 

아래 코드가 더 빠르다는 것을 알 수 있다. 하지만 이런 식의 방식은 좋지 않다. 여기서 시간의 문제가 있다.

1. 기기마다 다른 방식으로 시간을 기록한다. 물론 그렇다고 위 코드가 갑자기 반전되는 것은 아니다. 정확도에 문제가 된다는 것이다.
2. 위 실행 결과에도 알 수 있듯이 같은 기기여도 다른 시간을 기록한다. 큰 문제는 아니지만 완전히 신뢰할 순 없다.
3. 빠른 알고리즘의 경우 속도 측정이 충분히 정확하지 않을 수 있다. 아주 빠른 알고리즘이 세 개가 있다고 가정했을 때 그중에서도 빠른 게 있을 것이지만 타이밍 함수가 그런 작은 차이를 측정하기는 힘들다.

코드가 실행되는 시간을 측정하는 것이 나쁜 것은 아니지만 코드를 파일 안에 만들고 시간을 측정하는 방법 외에 더 좋은 방법이 있다. 이럴 때 사용하는 것이 big O 표기법이다. big O notation은 알고리즘의 복잡도를 입력의 크기에 따라 설명하기 위해 사용되는 수학적 표기법으로, 알고리즘의 성능이 입력의 크기가 커짐에 따라 어떻게 확장되는지 표현하는 표준화된 방법을 제공한다.

 

시간을 사용하지 않으면 무엇을 사용할까?  대신 컴퓨터가 처리해야 하는 연간의 개수를 센다.

처리하는 시간은 미미하게 변하더라도 그 시간은 항상 딱 정해진 연산의 개수에 달려있다. #2를 보면 n * (n + 1) / 2; 은 n이 크든 작든, 상관없이 연산이 3번 이루어진다. 

#1을 보면 n이 5라면 +연산이 5번, =이 5번이고, n이 20이라면 +가 20번, =이 20번 이루어진다. n개수만큼의 연산인 것이다.

#1은 5n+2의 연산을 수행한다. #1의 경우 n이 커질수록 연산의 개수도 비례적으로 늘어 난다.

중요한 것은 연산을 하나하나 세는 것이 아니라 전체적인 큰 그림이 중요하다. 큰 그림을 깨우쳐보자.

 

앞서 말했지만.

시간 복잡도란? 문제를 해결하는 데 걸리는 시간과 입력의 함수관계를 가리킨다.  시간 복잡도를  big O 표기법으로 나타낸다.

 

big O

알고리즘이 처리하는 데이터 양이 증가함에 따라 실행시간이 얼마나 걸릴지 혹은 얼마나 많은 메모리가 필요할지를 설명하는 공식적인 방식이다.

시간 복잡도 그래프

O(1) (Constant) Great

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타낸다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다. 위의 #2가 이에 해당한다.

 

O(log₂ n) (Logarithmic)  Good

입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 된다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.

 

O(n) (Linear) not bad

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 된다. 1차원 for문이 있다. 위의 #1은 정확하게는 5n+2지만  신경쓰는 것은 자릿수이기에 이에 해당한다.

 

O(n log₂ n) (Linear-Logarithmic) bad

데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적이다.

 

O(n²) (quadratic) very bad

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 된다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직하다.

 

O(2ⁿ) (Exponential) --------

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당된다.

 

그래프와 위 설명을 참고하여, 시간 복잡도에 따른 성능을 비교하면 아래와 같다.

faster O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ) slower

예시를 보자.

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

countUpAndDown(4)

실행 결과

첫 번째 for문에서 n이 커질수록 loop가 실행하는 횟수가 늘어나 O(n)을 가지고 두 번째 for문 또한 O(n)을 가짐.

그렇기에 빅오가 2n이라고 생각할 수 있지만 그걸 신경쓰지 않고 큰 그림인 O(n)라고 표현한다.

 

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

printAllPairs(2)

실행 결과

바깥 for에서 연산들이 n의 값만큼 늘어나 O(n)이고 안쪽 for문 또한 O(n)이다. 이것은 중첩되어 있어서 O(n)으로 단순화되는 O(2n)이 아닌 O(n*n) 즉, O(n²)이다.

 

O(2n) -> O(n)

O(500) -> O(1)

O(13n²) -> O(n²)

O(n + 10) -> O(n)

O(1000n + 50) -> O(n)

 

bigO 쉽게 적용할 수 있는 규칙

1. 산술 연산은 일정하다. 즉, 상수이다. n의 값으로 무엇이 오든 속도에는 상관없다. 2+2처리시간과 100만+2 처리 시간은 비슷하다.
2. 변수 할당은 일정하다. 컴퓨터가 변수에 값을 할당하는데 걸리는 시간은 비슷하다. x=1000, x=100만 처리 시간은 비슷하다.
3. 배열(by index) 또는 객체(by key)의 요소에 접근하는 것은 일정하다. 첫 번째 아이템을 찾던지, 100번째 아이템을 찾던지 index 사용하면 같은 시간이 걸림.
4. loop에서 복잡도는 loop의 길이에 loop내부에서 일어나는 모든 것의 복잡도를 곱한 것. 0에서 n까지 간다면, n이 커질 수록 loop 반복 횟수는 증가한다. 만약 중첩 루프가 있다면 n제곱 실행 시간이 될 수 있다.

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

5보다 작은 수를 입력해도 무조건 5까지 출력되고 5이상의 n을 입력하면 n만큼 입력하는 함수이다.

결국 5까지 반복하거나 n까지 반복할 것이다. 주목해야할 점은 n이 더 커지고 커지는 경우이다. 그러면 실행 시간은?

n이 1000이면 1000번 반복될 것이다. 빅오는 O(n)이다.

 

위 코드와 반대인 아래를 보자.

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

n의 값에 상관 없이 최대 5까지만 출력될 것이다. n이 커져도 아무 영향이 없다. 해당 loop는 5번까지만 반복되고 빅오는 O(1)이다.

 

공간 복잡도란? 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다.

다음 시간에 알아보자.