[알고리즘] Big O Notation

Big O Notation이란?

알고리즘의 효율성을 표기해주는 표기법이다. 예를 들면 문자열을 거꾸로 출력하는 방법에만 해도 10가지가 넘는다. 그중에서 어떤 것이 제일 좋은 방법일까? 빅오 표기법 은 이것을 평가하는 척도이다.

아래 두 예제를 보면 아래의 코드가 훨씬 빠르다는 걸 볼 수 있다.

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.4791465000025927 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.000028100002557039262 seconds

시간 복잡도

시간 복잡도(Time Complexity)는 알고리즘의 실행 속도를 말한다 빅오표기법으로 시간 복잡도 성능을 아래와 같이 표기할 수 있다.

O(n)

function item(n){
	for(var i=1; i<=Math.max(5,n); i++{
    	console.log(i)
    }
}

O(1)

function item(n){
	for(var i=1; i<=Math.min(5,n); i++{
    	console.log(i)
    }
}

공간 복잡도

입력 받는 데이터와 관련 없이 알고리즘 그 자체의 메모리 공간 크기를 다룬다

• boolean, 숫자, undefined, null -> O(1) 공간
• 문자열 -> O(n) 공간
  • 길이가 50자인 문자열은 1자인 문자열보다 50배 더 많은 공간을 차지한다 배열, 객체 -> O(n) 공간
  • n은 배열의 길이이거나 키 값의 개수

function double(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(2 * arr[i]);
  }
  return newArr;
}
// 전체적으로 주어진 배열의 길이에 따라 메모리공간이 결정되므로// O(N)의 공간복잡도

function sum(arr) {
  let total = 0;// O(1)for(let i = 0; i < arr.length; i++) {// O(1)
    total += arr[i];// 메모리 안따짐
  }
  return total;
}
// 총 공간복잡도: O(1)