01 빅오 표기법(Big O)

1.1 빅오 표기법의 필요성 

  동일한 동작을 구현하기 위한 코드는 수많은 방법으로 작성이 가능하다. 그렇다면 이 많은 코드들 중에서 상황에 알맞는 성능이 가장 좋은 코드는 무엇인지를 확인하기 위한 방법이 빅오 표기법이다. 동일한 동작을 구현하기 위한 여러 코드 작성 방법은 그 작성 방법마다 장단점을 가지고 있다. 하지만 개발자는 이를 비교해보고 확인하는것이 중요하다. 그리고 디버그시 코드를 느리게 만드는 것이 무엇인지 이해하는것도 굉장히 중요하다. 그렇기 때문에 빅오 표기법이 필요하다.

 

1.2 코드 시간 재기

  코드를 작성함에 있어서 더 좋은 코드를 판단하는 기준은 무엇일까? 처리 속도가 얼마나 빠른지? 메모리가 얼마나 사용되고 있는지? 아니면 가독성이 좋은 좋은 코드? 이 처럼 좋은 코드를 평가하는 기준은 매우 다를 수 있다. 우선 속도를 기준으로 좋은 코드를 판별해 보려고 한다.

//숫자 1부터 특정한 n숫자 사이에 있는 모든 숫자들을 더하는 함수작성

// 1번 예제
function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}
console.log(addUpTo(10));
//함수 처리 시간이 약 1.2초 걸림

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



//2번 예제
function addUpTo(n) {
  return n * (n + 1) / 2;
}
//함수 처리 시간이 약 0.0001초 걸림
var time1 = performance.now();
addUpTo(1000000000);
var time2 = performance.now();
console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`)

//하지만 이렇게 하나 하나 걸리는 시간을 메서드로 확인하는것은 굉장히 비효율적인 일임

  위 예제 1번 코드는 반복문을 통해서 함수를 작성했고, 예제 2번은 수학 공식을 사용해서 함수를 작성한 후, 처리되는 시간을 함수별로 메서드를 통해 비교해 본 것이다. 여기서 중요한것은 어떻게 작성한 함수가 더 빠르게 처리되느냐가 아니다. 물론 2번 예제가 더 빠르고 결국 빠르기를 기준으로 본다면 좋은 코드일 것이다. 그치만 여기서 중요한것은 위의 코드들처럼 하나하나 메서드들을 통해서 비교하는것은 굉장히 비효율적이라는 것이다. 예를들어 극단적이지만 처리하는데 1시간이 걸리는 코드와 4시간이 걸리는 코드 중 누가 더 빠르게 처리되는지를 비교하기 위해서는 시간이 너무 많이들고, 반대로 처리가 너무 빨라 비교가 힘든 경우도 있을 수 있다. 또 컴퓨터 성능별로도 차이 등 많은 변수들이 있을 수 있다. 그렇기 때문에 빠르기를 기준으로 상황에 적합한 좋은 코드를 판별하기는 어렵다. 그렇기 때문에 빅오 표기법이 필요한 것이다.

 

1.3 연산 개수 세기

  바로 위에서 살펴본바와 같이 시간으로 코드를 비교하는것은 문제가 있다. '그렇다면 뭐가 좋을까?' 바로 연산 개수를 세는 방법이다. 

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




//2번 예제
function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
    total += i;
    }
    return total;
}

 위의 코드를 비교해 보자. 1번 예제 함수의 연산 개수를 확인해 보면 곱하기, 더하기 그리고 나누기 연산자를 갖고 총 3번의 연산을 하게 된다. 예제 2번 함수는 반복문이 포함되어 있기 때문에 총 5n+2번의 연산이 이뤄진다. (n번의 + 연산, n번의 할당, n번의 증감 등) 또 이와같이 모든 연산을 하나 하나 카운트해서 비교하는것도 굉장히 어려운 일이다. 그렇기 때문에 전체적인 추세를 보는것이 굉장히 중요하다. 전체적인 추세를 알려주는 것이 바로 빅오 표기법이다.

 

1.4 시간 복잡도 시각화 하기

  다음은 현재 공부하고있는 해당 강의의 강사님이 만들어 놓은 n값을 함수에 할당 했을때의 연산되는 시간을 시각해 놓은 페이지다.

https://rithmschool.github.io/function-timer-demo/

Big O Introduction

  해당 페이지에 들어가서 함수 별로 n값을 입력했을때의 연산 시간을 확인해 볼 수있다.  

시간 복잡도 시각화

  위의 사진 처럼 작성된 코드에 따라 연산하는데까지 걸리는 시간이 다르다. 빅오 표기법은 입력된 내용이 늘어날수록 알고리즘에 실행 시간이 어떻게 변화하는지 설명하는 공식적인 방법이다. 빅오 표기법은 전반적인 추세에 주목하는 것이다. 다음은 빅오 표기법으로 함수를 표현해보자.

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

  위 코드의 n의 크기가 커져도 연산해야 하는 횟수는 3번으로 정해져 있기 때문에 처리되는 시간은 동일하다.(약 0.0002초) 이를 상수라고 표현하며 빅오 표기법으로는 O(1)이라 표현한다.(위 그래프의 파란색 추세선이다.)

function addUpToFirst(n) {
    var total = 0;
    for (var i = 0; i <= n; i++) {
        total += i;
    }
    return total;
}

  위 코드의 n의 크기가 커지면 커질수록 연산해야 하는 횟수도 증가하기 때문에 처리되는 시간도 비례해서 같이 늘어난다. 이를 빅오 표기법으로는 O(N)이라 표현한다.(위 그래프의 초록색 추세선이다.)

function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i < n; i++) {
        console.log(i);
     } //O(N)
    console.log("At the top!\nGoing down...");
    for (var j = n - 1; j >= 0; j--) {
        console.log(j);
    } //O(N)    ---> 그렇다고 O(2N)이라 하지 않음
    console.log("Back down. Bye!");
}

  한 가지 주의해야 할 점은 N(연산 횟수)이 2N이든 5N이든 O(N)으로 표시한다. 앞에서 언급했듯이 빅오 표기법은 전반적인 추세를 확인하는 것이고, 그래프로 확인했듯이 변함이 생기지 않기 때문이다. 수학적으로도 n의 값에 1억을 넣더라도, 추세선은 변함이 없기 때문에 이를 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^2)이라 표현한다. (위 그래프의 빨간색 추세선이다.)

 

1.6 빅오 표기법 단순화

  다음으로는 빅오 표기법을 단순화한 예시들을 살펴보자.

 

1. O(2N) --> O(N)

2. O(500) --> O(1)

3. O(13N제곱) --> O(N제곱)

4. O(N + 10) --> O(N)

5. O(1000N + 50) --> O(N)

6. O(N제곱 + 5N + 8) --> O(N제곱)

 

  위의 예제들처럼 단순화할 수 있는 이유는 추세선이기 때문이다. 빅오 표기법은 추세를 확인하는 것이다. 연산하는 횟수가 무한대로 증가했을때도 추세선에는 변함이 없을 것이기 때문이다.

 

1.7 공간 복잡도

  이전까지는 입력이 커질수록 알고리즘의 실행속도가 어떻게 바뀌는지 분석한 시간 복잡도에 대해서 배웠다면 지금부터 확인할 내용은 입력이 커질수록 알고리즘이 얼마나 많은 공간을 메모리 공간을 차지하는지를 기준으로 빅오 표기법를 표현하는 방법에 대해서 보려고 한다.

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

  위 코드에서 공간을 차지하는 것은 total과 i변수다. 매개변수 arr에 어떤 값이 인수로 전달되어도 저장되는 공간은 계속해서 일정하다. 따라서 변수 total과 i의 공간은 계속 상수로 존재한다. 빅오 표기법으로는 O(1)로 표현한다.

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

   위 코드의 경우 매개변수 arr에 인수로 전달되는 값이 크면 클수록 변수 newArr의 공간이 저장되는 메모리 공간이 커진다. 즉 비례하여 증가한다. 이를 빅오 표기법으로는 O(N)이라 표현한다.

 

<빅오 표기법> 시간 복잡도