Big O 표기법

Big O 표기법이란?

알고리즘의 효율성을 표기해주는 표기법을 뜻한다. 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용되며,

시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.

 

(여기서 말하는 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 떄 덧셈, 뺄셈, 곱센 같은 기본 연산의 횟수를 뜻한다.)

 

Time Complexity

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

이 경우 빅오표기법으로 나타냈을때 알고리즘의 효율성은 O(1) 이다.

 

 

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

이 경우 빅오표기법으로 나타냈을 때 알고리즘의 효율성은 O(n)이다.

5n 이 아니라 n인 이유는 궁극적으로 그래프를 그렸을 때 별 차이가 없기때문에 단순히 n 으로 표기한다. 

=> 상수는 중요하지 않다. (Constnats Don't Matter)

 

 

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^2) 이다.

 

 

Constants Don't Matter

O(2n) -> O(n)

O(500) -> O(1)

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

 

 

 

 

Space Complexity

Auxiliary space complexity (보조 공간 복잡도) 란?

입력되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간을 의미한다.

즉, 임시로 사용하는 공간이기 때문에 input의 size를 포함하지 않고 문제 해결을 위해 중간에 사용하는 버퍼 공간을 말한다.

 

Space Complexity (공간 복잡도) 란?

input size를 고려하여 알고리즘이 문제를 해결하기 위해 사용하는 모든 공간을 의미한다.

즉, 공간 복잡도(Space Complexity)는 보조 공간(Auxiliary Space)와는 다르게 'input size'를 포함한다.

 

booleans, numbers, undefined, null은 Constants space 다.

반면 string은 문자열의 길이(n) 만큼 O(n)의 공간을 필요로 한다. 

reference type, array, object도 동일하게 대부분 O(n)으로 본다. (n은 배열의 길이나 객체의 키 개수일 수 있다.)

 

공간복잡도는 O(1) 이다.

 

공간복잡도는 O(n) 이다.

Logarithms

로그함수란?

지수함수의 역함수.

파란게 로그함수. 빨간게 지수함수.

 

 

 

정리

- 알고리즘의 성능을 분석하기 위해서는 빅오 표기법을 사용한다.

- 빅오 표기법을 통해서 시간과 공간 복잡도에 대한 이해를 높일 수 있다.

- 정확도가 아니라 전체적인 추세가 중요하다.

- 빅오 표기법으로 측정되는 알고리즘의 시간과 공간의 복잡도는 하드웨어의 영향을 받지 않는다.

(빅오는 연산의 개수를 따지기 때문)

 

 

 

본 내용은 작성자가 (Udemy) JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 듣고 정리 및 메모한 내용입니다.  오역 및 오개념이 있을 수 있으니 바로잡기 위해 문제가 있는 경우 댓글 남겨주시면 매우 감사하겠습니다.

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

JavaScript (JS) Algorithms and Data Structures Masterclass