[JS] 알고리즘&자료구조 - 01. 빅오표기법(Big-O)

chael_lo·2022년 5월 17일
Big OJavaScriptalgorithmjsstructures알고리즘자료구조
0

알고리즘&자료구조

목록 보기
1/1

빅오 표기법(Big-O)

정식으로 입력된 내용이 늘어날수록 알고리즘에 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식이다.
코드 분류, 숫자로 코드의 성능을 빅오 형식으로 표기할 수 있다.

좋은 코드 기준

좋은 코드의 기준은 뭘까? 브라우저에서 실행되는 속도, 코드의 간결성 등 기준은 많다.
그 기준을 측정하기 위하여 브라우저의 내장 객체인 performance를 이용해 동일한 기능을 담은 두 개의 함수에서 함수 실행 시간을 측정해 보았다.

addUpTo 함수 실행 전과 후에 performance.now()를 실행하여 그 시간만큼 빼주었다.

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

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

실행 결과

  • Time Elapsed: 1.256199999988079 seconds.
  • Time Elapsed: 1.1455 seconds.
  • Time Elapsed: 1.1331000000238418 seconds.
  • Time Elapsed: 1.1985999999642372 seconds.
function addUpTo(n) {
  return n * (n + 1) / 2;
}

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

실행 결과

  • Time Elapsed: 0.00010000002384185791 seconds.
  • Time Elapsed: 0.00009999996423721313 seconds.
  • Time Elapsed: 0.00010000002384185791 seconds.
  • Time Elapsed: 0 seconds.

결과만 보면 뒤의 함수가 더 좋은 코드라고 할 수 있다.
하지만 책정된 시간이 매번 다르고, 기기사양에 따라서도 결과는 달라질 수 있기 때문에 좋은 코드라고 말할 수 있는 정확성이 떨어진다. 게다가 빠른 알고리즘에서는 정말 짧은 시간안에 처리되기 때문에 속도 측정 정확도가 떨어질 수 있다.

그래서 빅오 표기법에서는 시간 복잡도와 공간 복잡도를 기준으로 좋은 코드를 판단한다.

시간 복잡도

시간 복잡도는 함수를 컴퓨터가 실행해야 하는 연산의 갯수의 관점에서 본다.
연산의 갯수와 n의 값에 따른 연산 횟수를 따져보며 연산에 걸리는 시간을 유추한다.


아래의 함수는 n의 값과 상관없이 3번의 연산을 한다. 
function addUpTo(n) {//3번의 연산(덧셈 1, 곱하기 1, 나누기 1) 
  return n * (n + 1) / 2;
}

아래의 함수는 n이 커질수록 연산의 갯수도 비례적으로 늘어난다.
실제로 연산에 걸리는 시간도 늘어나며 연산의 갯수는 궁극적으로 n의 곱과 연관 되어 있다. 
function addUpTo(n) {//셀 수 없는 연산..(딱봐도 세기 귀찮은 연산 횟수)
    let total = 0;//= 도 연산(비교, comparisons)
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

O(1) > O(n) > O(n의 제곱)

빅오(O = f(n))는 어떤 함수에 입력한 값이 늘어나는 것과 함수 실행 시간이 변하는 관계를 의미한다.

  • O(1):n의 값과 상관없이 실행 시간은 변함이 없다.
    • 예시) n의 값과 상관없이 3번의 연산이 있는 함수
    • 연산과 상관없는 n을 1이라고 표현한다.
  • O(n):n의 값과 실행 시간이 관련되어 있다.
    • n이 커질수록 실행 시간이 늘어난다.
    • 2n, 5n, 10n일 경우도 큰 의미에서 같기 때문에 n으로 표현한다.
    • 예시) 하나의 함수에서 두번의 반복분
  • O(n의 제곱): n이 커질수록 실행 시간이 n의 제곱으로 늘어난다.
    • 예시) 중첩 반복문

공간 복잡도

공간 복잡도는 n이 커질수록 입력이 커진다는 것을 가정하며 함수를 사용되는 메모리의 양,즉 알고리즘 자체가 필요로 하는 공간의 관점에서 본다.

  • 불변 공간(booleans, numbers, undefined, null)
    입력하는 크기와 상관없이 똑같다.
  • O(n) 문자열 공간(문자열 길이만큼)
    • 50자의 문자열이라면 1자의 문자열보다 50배의 공간을 차지 한다.
  • O(n) reference type 배열의 길이, 객체의 갯수
    • 배열 길이가 4인 배열은 배열 길이가 2인 배열의 2배의 공간을 차지한다.

아래의 함수는 두 변수 이외에 새로 할당하는 변수가 없고 arr의 크기와 상관없이 항상 똑같다. 입력의 크기가 차지하는 공간과는 관계가 없다. 
function sum(arr) {//O(1)의 공간 차지
    let total = 0;
    for (let i = 0; i <= arr.length; i++) {
        total += arr[i];
    }
    return total;
}

아래의 함수에서 차지하는 공간은 arr(입력된 배열)의 크기에 비례해서 커진다.

function double(arr) {//O(n)의 공간 차지
    let newArr = [];
    for (let i = 0; i <= arr.length; i++) {
        newArr.push(2 * arr[i]);
    }
    return newArr;
}

로그

로그, 로그함수는 지수함수의 역함이다.
시간 복잡도와 공간복잡도 외에 로그로 알고리즘을 평가할 수 있다.
곱셈을 덧셈으로 변환시켜 매우 큰 수 또는 작은 수를 계산하는데 편리함을 주는 수 표현 방식이다.

데이터가 2배로 증가할 때, 연산수가 1 단계 씩 늘어나는 형태를 말한다.
데이터가 많아질수록 성능이 우수하다.

로그 계산법

그 숫자가 1보다 작아지기 전에 2로 나눠지는 횟수다.

  • 8 -> log(8) = 3
  • 25 -> log(25) = 4.64

로그 함수 형태의 알고리즘 표기

O(log n)

정리

  • 알고리즘 성능을 분석하기 위해서는 빅오 표현법을 사용한다.
  • 입력의 크기가 늘어날수록 전체적인 추세와 관련 되어 있다.
  • 빅오로 측정된 알고리즘의 시간, 공간 복잡도는 하드웨어에 영향을 받지 않는다.
    (연산의 갯수를 따지기 때문)
  • 빅오는 정확도가 아니라 전체적인 추세를 중요하게 생각한다.
    • 예시) 이 함수는 대략 연산 횟수는 이렇고 변수의 크기와 갯수가 이렇기 때문에 저 함수보다 실행속도가 더 빠르겠군!

공부 키워드

  • Big-O, 빅오 표기법
  • 시간복잡도, 공간복잡도
  • 로그 시간 알고리즘

출처: JavaScript 알고리즘 & 자료구조 마스터클래스 - 빅오 표기법
깃정리: https://github.com/jcrs0907/js_algorithm_structures

profile
chael_lo
천천히 꾸준히

0개의 댓글