Big O 표기법이란? 자바스크립트 예제로 알아보자!

Big O natation

Big O 표기법의 필요성

• 여러가지 코드를 서로 비교하고 성능을 평가하기 위해서
• 왜 중요한가?
  1. 코드챌린지, 면접, 큰 데이터셋을 다루는 기업에서 성능이 좋은 코드가 필요하기 때문에 정확한 전문용어를 사용하는 것이 중요함.
  2. 여러 접근법의 장단점을 알 수 있음.
  3. 비효율적인 코드를 찾는데 도움이 됨.

간단하게 Big O 표기법을 표현하는 방법

1~n까지 모두 더하는 function 만들기

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

//등차수열을 이용한 함수
function addUpTo2(n) {
return n*(n+1)/2
}

let t1 = performance.now(); // 브라우저가 이 문서를 만든 시간을 알려줌
addUpTo(1000000000); // 큰 숫자 입력
let t2 = performance.now(); // 앞 줄의 기능을 한 후 문서를 연 시간
console.log(`시간 경과는 ${(t2-t1)/1000} 초이다.`)

• addUpto1 : 1.9초, addUpto2 : 0초
  속도는 addUpto2가 더 빠르지만 이것만으로 좋은 코드다.라고 결론 지을 수 없음.
  • 속도를 기준으로 비교할때 발생하는 문제점.
    1. 기기 사양을 고려하지 않음.
    2. 같은 기계더라도 다른 시간을 기록할 수 있음.
    3. 너무 빠른 알고리즘일 경우 속도 측정 정확도가 충분하지 않을 수도 있음.
  • 해결책
    • 정확한 시간을 초로 측정하기 보다는 컴퓨터가 처리해야할 연산 개수를 센다.

    function addUpTo1(n) {
      let sum =0; // 1 assignment
      for(let i =1;i<=n;i++){ // 1개의 = 과 n개의 비교, n개의 덧셈과 =
        sum += i // n개의 덧셈과 n개의 =
      }
      return sum
    } 

    • 대략 5n+2개의 연산이 들어가 있다.

    function addUpTo2(n) {
    return n*(n+1)/2 // 곱셈,덧셈,나눗셈 
    } 

    • 3개의 연산이 들어가 있다.

객관적으로 비교할 수 있는 특정한 값이 필요하기 때문에 빅오표기법이 필요함.

빅오 표기법

• 개념 : 입력의 크기와 실행시간 또는 공간 복잡도의 관계를 뜻함.
• 장점 : 하드웨어의 영향을 받지 않음.
• 표현 : O(f(n))
  • f(n) = n : 선형(n값이 커질수록 실행 시간 또는 공간 복잡도가 높아짐.)
  • f(n) = n^2 : 반복문이 두 번 있는 case 임으로 실행시간이 엄청 늘어남.
  • f(n) = 1 : n값이 변해도 결과값에 아무 영향을 끼치지 않음.
• 간단하게 빅오 표기하기
  • O(2n) => O(n)
  • O(500) => O(1)
  • O(2n^2) => O(n^2)
  • O(n^2+2n-8) => O(n^2)

시간 복잡성과 공간 복잡성

시간 복잡성

시간 복잡성을 구하는 요령

1. 연산(덧셈,뺄셈,곱셈,나눗셈)은 상수임. O(1)
2. 변수 배정도 상수임. O(1)
3. 인덱스를 이용해서 배열 값을 찾거나 key를 사용하여 객체 값을 찾는 것도상수이다. O(1)
4. 루프가 있으면 복잡도가 (루프의 길이 * 루프 안에 연산)임으로 n이 커질수록 복잡도가 커짐. O(n)
5. 중첩 루프이면 n제곱 실행 시간임. O(n^2)

공간 복잡성

• 입력값이 커질수록 얼마나 많은 공간을 차지하는지를 알 수 있음.공간 복잡성을 구하는 요령

1. 입력이 차지하는 공간은 상관 없음.

2. booleans, numbers, undefined, null은 모두 상수 공간임.O(1)

3. 문자열,reference타입,배열,객체 은 O(n)임

빅오 표기법을 사용해서 여러 알고리즘 평가하기

1.아래 함수에 대한 공간 복잡도를 구하세요.

function logUpTo(n) {
    for (var i = 1; i <= n; i++) {
        console.log(i);
    }
}

단순히 숫자만 출력하기 때문에 공간 복잡도는 O(1)이다.

 

2.아래 함수에 대한 시간 복잡도를 구하세요.

function subtotals(array) {
    var subtotalArray = Array(array.length);
    for (var i = 0; i < array.length; i++) {
        var subtotal = 0;
        for (var j = 0; j <= i; j++) {
            subtotal += array[j];
        }
        subtotalArray[i] = subtotal;
    }
    return subtotalArray;
}

중첩 반복문을 사용하므로 시간 복잡도는 O(n^2)이다.

 

출처 : https://www.udemy.com/course/best-javascript-data-structures/