Big O notation

이번 포스트에서는 어떠한 문제에 대한 여러 해결법중 제일 효율적인 해결법을 찾기 위한 방법인 Big O notation에 대해 알아보겠다.

 

알고리즘에따라 많은 데이터량을 다루는 것을 잘 할수도 있고 처리시간이 좀 더 걸리더라도 데이터량에 관계없이 처리속도가 일정할수도 있다. 또한 이렇게 시간이 기준이 아닌 메모리 할당, 즉 메모리 공간을 기준으로 효율을 측정할 수도 있다.

 

이러한 효율을 측정하는 기준이 시간복잡도 혹은 공간복잡도이며 복잡도를 표현하는 방식은

• Big-O(빅-오) : 최악의 경우를 표현
• Big-Ω(빅-오메가) : 최선의 경우를 표현
• Big-θ(빅-세타) : 평균의 경우를 표현

이렇게 3가지가 존재한다.

 

위의 3가지중 대부분 Big-O notation을 사용하는데, 이는 어떠한 알고리즘의 최악의 경우를 고려하여 대비하기 위해서 이다.

 

이렇게 코드를 작성할때 혹은 디버깅할때 코드를 느리게 만드는 원인을 찾아내데 Big O notation을 사용한다.

 

 

더 좋은 코드란?

실행속도가 빠른 코드, 메모리사용이 적은 코드, 가독성이 좋은 코드가 말그대로 '좋은코드'가 될수 있는데 만약 실행속도가 빠른 코드를 찾는다고 가정해보자.

 

임의의 숫자를 입력햇을때 입력값의 이전의 모든 양의 정수들을 더하는 두가지 함수를 만들어봤다.

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

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

// 속도측정
let t1 = performance.now();
iterator(10000000);
let t2 = performance.now();

let t3 = performance.now();
formular(10000000);
let t4 = performance.now();

console.log(`반복문의 실행시간입니다. ${(t2 - t1) / 1000}`);
console.log(`공식의 실행시간입니다. ${(t4 - t3) / 1000}`);

첫번째 함수는 반복문을 사용하였고 두번째는 공식을 이용한 함수를 만들었다.

그후 실제속도를 측정해보면

위와 같이 직접 실행하는 속도를 측정할수 있었다.

하지만 모든코드를 이런식으로 측정하는것은 너무 비효율적이고

컴퓨터들의 사양에 따라 즉 사용자에 따라 측정 속도가 조금씩 차이가 날수도 있을것이다.

 

위와 같은 단점들로 직접적인 실행 시간을 측정하기보다

코드가 실행되는 동안 연산되는 횟수를 파악하여 속도를 어느정도 예상하고 비교 할수도 있는데

 

예를들어 위의 함수들을 이용해 비교해보면 함수 formular는 어떠한 입력값이 들어오든 곱하기, 더하기, 나누기 이렇게 3번의 연산만을 사용하게 된다.

 

함수 iterator의 경우는 for문으로 반복하여 연산하기 때문에 입력값 n에 따라 연산횟수가 늘어나며 시간도 더 오래 걸리게 될것이다.

 

 

Big O notation의 시간복잡도

빅오 표기법을 활용하면 이처럼 연산횟수를 통해 어떠한 함수의 입력값에 따라 대략적인 연산시간을 시각화하고 비교할수 있다.

예를 들자면, 함수 fomular의 경우 입력값이 얼마가오든 항상 같은 연산횟수를 가지므로 빅오 표기법으로는 O(1)이 된다.

함수 iterator의 경우 입력값 n에따라 연산횟수가 증가하며 그에따른 실행속도또한 증가하게되며

이것을 빅오 표기법으로 표현하면 O(n)이 된다.

Big O 표기법의 시간복잡도

O(n²) 예시

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

위와같이 반복문안에 반복문을 작성을 하고 입력값으로 3이 주어졌을경우

첫번째 반복문에서 i = 0에서 시작하여 두번째 반복문을 j = 0~2까지 실행하고

다시 첫번째 반복문에서 i = 1에서 두번째 반복문 j = 0~2까지 실행

마지막으로 i = 2 에서 j = 0~2까지 실행하므로

총 9번의 연산을 하게된다.

 

이경우의 시간복잡도를 빅오로 표현하면 O(n²)이 된다.

 

 

빅오 표현식 단순화 하기

상수는 빅오 시간복잡도를 표현하는데 그렇게 도움이 되지않는다 예를들어

O(2n)이라는 시간 복잡도가 있고 만약 이것을 그래프로 표현하게된다면 증가폭이 일정한 선형 그래프가 될것이다.

O(n)또한 마친가지 이기때문에 상수 2를 버리고 O(n)으로 표현한다.

 

O(200) 또한 상수 500이 가지는 의미는 크지않다 어떤한 입력값이 오더라도 걸리는 시간의 값은 같으므로

O(1)로 표현한다.

 

O(5n²)의 경우도 상수 5가 가지는 의미는 크지않기에 O(n²)으로 표현해준다.

이를 통해 알수 있는것은 빅오 표현식으로 코드가 실행되는 정확한 시간을 구하는것이 아닌

입력값에 따른 시간의 변화를 시각화 한다는 것이 중요한것 같다.

(O(5n²)과 O(n²)의 그래프의 모양은 같기때문)

 

마찬가지로 O(n² + 5n + 8)의 경우 그래프의 모양은 O(n²)과 같으므로 O(n²)으로 단순화하여 표현한다.

 

 

공간 복잡도

공간 복잡도는 메모리 할당과 사용에 해당된다.

자바스크립트에서 boolean, number, undefined, null은 모두 어떠한 값이오든 공간의 크기의 값은항상 일정 하지만 string의 경우 문자열의 길이에 따라 공간값이 달라지게 된다.

또한 array와 object도 안의 내용량에 따라 할당받는 공간값이 달라지게 된다.

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

위의 경우 함수 sum안에서 let total과 let i의 숫자로된 공간만 할당받으며 숫자의 경우 할당받는 메모리의 크기는 변하지 않으므로 빅오 공간복잡도는 O(1)이 된다.

 

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

위의 함수 push는 함수 sum과는 비슷하지만 조금 다르다.

let total이라는 숫자로된 변수가아닌 newArr라는 array를 할당받고 있다.

입력받은 arr의 길이에따라 newArr의 길이가 달라지기에 이경우 빅오 공간복잡도는 O(n)이 된다.

 

 

로그

log는 제곱의 반대 표현이다.

 

2²=4의경우 log₂(4)=2와 같다.

 

위의 빅오 표기법의 그래프를 확인해보면 n²의 반대인 log n의 값을 가진 알고리즘의 경우 굉장히 좋은 효율을 보여주고 있다.

 

 

마무리

어떠한 알고리즘의 성능을 분석하기 위해 Big O notation을 사용하며 시간복잡도 혹은 공간복잡도로 분석이 가능하다.

Big O notation은 정확한 시간이나 공간 할당량을 계산하는것이 아닌 그래프를 통한 전체적인 추세 혹은 효율을 시각화 한다.