[알고리즘] 빅오표기법 - 1

*강의를 보고 정리한 노트입니다. 

 

알고리즘의 복잡도를 판단하는 척도로는 시간 복잡도와 공간 복잡도 두 가지가 있는데, 빅 오 표기법은 시간 복잡도를 다룬다. 

 

 

하나의 문제를 해결하기 위한 해결법은 무수히 존재하고 다양한데, 그 중에서 가장 좋은 방법으로 해결할 수 있는 하나의 방법은 무엇일까?

 

 

예를 들어보자면,

문제를 접근하는 두가지 방식의 예시가 있습니다. 첫번째는 루프, 두번째는 리스트로 문제를 해결할 수 있다고 가정해봅니다. 루프와 리스트 둘 중에서 과연 뭐가 더 좋은 선택일까?  바로 이것이 빅오표기법의 궁극적인 목표입니다. 

 

 

즉, 여라가지 코드를 일반적으로 서로 비교하고 성능을 평가하는 방법.

 

 

근데, 제대로 동작하기만 하면되는데 왜 제일 좋은 해결책을 찾는걸까?

 

그것은 바로, 수천개, 혹은 아주 큰 데이터셋을 다루는 기업에서 한 알고리즘이 다른 알고리즘 보다 한시간이나 빠르다면 해당 빠른 알고리즘을 선택하지 않을 이유가 없죠.

 

 

하지만! 모든 해결책은 항상 장점과 단점이 존재하기 마련입니다. 위에서 말하는 한시간이나 빠른 알고리즘 또한 그것이 무조건 최고라고 볼수는 없을 것입니다. 

 

 

그렇다면 이제 빅오표기법 작성 방식에 대해 살펴보겠습니다.

 

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

 

위의 함수의 첫번째줄부터 내려와보겠습니다. 총 값을 담는 total 변수가 있고 (1개의 연산 ' = '), 

for문안에 i라는 변수를 선언하였고 (1개의 연산 '='), n개 만큼의 i가 연산이 되어지게 되고 (n개 연산), i에 하나씩 더해줍니다( '++' ) 그리고 total에 값이 담아집니다(n개 연산). 그리고 제일 중요하게 볼 부분은 for 루프입니다. 즉 n이 늘어날수록 연산이 급격하게 늘어나게 됩니다. 

 

위의 예시의 연산의 갯수는 즉, n에 달려있고 O(n)으로 표기합니다.

 

 

그렇다면 중첩 for문의 예시를 들어보겠습니다.

 

 

function print (n) {
    for (let i=0; i<n; i++) {            -------- O(n) 
       for (let j=0; j<n; j++) {         --- O(n)   |
           console.log(i,j);                  |     |
       }                                 -----      |
    }                                    ------------
}

 

위의 예시는 for문안에 for문인 중첩 루프입니다. 이 경우에 O(n*n)이 되어지기 때문에 간단하게 O(n^2) 으로 표기하게 됩니다.  

 

 

 

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

 

이번에는 다른예시로 n개 만큼 더해주는 for문을 조금 더 다른 방법으로 만들어진 예시입니다. 위의 예시에는 3개의 연산이 존재합니다. 

* + / 3개의 연산이 존재하지만 간략하게 표기해주는 빅오표기법으로는 O(1)으로 표기해줍니다.  

 

 

 

위의 예시들 처럼 빅오표기법은 연산의 갯수는 크게 중요하지 않고 큰 그림을 보아야 합니다. 연산이 몇개이든 아주 멀리서 해당 그래프를 보게된다면 그래프 모양은 동일 할 것이기 때문입니다.

 

 

O(2n)       ---->   O(n) 

O(500)     ---->  O(1)

O(13n^2)    ----> O(n^2)

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

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

O(n^2 + 5n + 8)    ----> O(n^2)     다른 연산과 n제곱 연산이 있다고하여도 여기서 중요한 것은 n의 제곱이기 때문에 빅오 표기법에서는 O(n^2)으로 표기합니다.