[알고리즘] 1. BigO

BigO가 필요한 이유

좋은 코드란 속도, 효율(메모리), 가독성 등을 고려한다. 우선 속도를 평가하는 것에 집중해보자.

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

위와 같은 방법으로 두 코드의 실행 속도를 비교해볼 수 있다. 하지만 이런 방식은 다음의 이유로 문제가 있다.

1. 기기마다 다른 방식으로 시간을 기록한다.
2. 같은 기기라도 다른 시간을 기록한다.
3. 빠른 알고리즘에서는 정말 짧은 시간에 코드가 처리되기 때문에 속도 측정이 어려울 수 있다.

연산 갯수 세기

코드가 실행될 때 걸리는 정확한 시간을 측정하는 방법 대신 컴퓨터가 처리해야하는 연산의 갯수를 세면 된다.

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

위 코드에서 연산자는 +도 있고 =도 볼 수 있다. 또한 for문 안에 있는 연산자는 * n번의 연산이 일어난다. 물론 코드에서 연산자만 골라 세는데에 하루종일 시간을 쓰자는 뜻은 아니다. BigO 표현을 사용해서 연산 갯수의 전체적인 추세를 시각화해서 비교해볼 수 있다.

시간 복잡도를 BigO로 표기하는 법

1. O(n)

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

2. O(n^2)

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

3. O(1)

for (var i = 1; i <= Math.min(n, 10); i++) {
  console.log(i);
}
// n이 아무리 증가해도 for의 반복횟수는 최대 10

단순화

1. 상수항 무시

O(100) => O(1)
O(2n) => O(n)
O(10n^2) => O(n^2)

2. 최고차항만 표시

O(5n + 10) => O(n)
O(n^2 + 2n + 5) => O(n^2)

공간 복잡도

입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는 지에 대해 알아보도록 하자.

1. 문자열을 제외한 원시타입

• boolean, number, undefined, null
• 고정 공간(constant space)이란 입력 값, 알고리즘 실행과는 관련 없이 사용되는 공간
• 고정 공간은 c(상수)라고 할 수 있으며 O(1)이다

2. 문자열

• 50자인 문자열은 길이가 1자인 문자열보다 50배 더 많은 공간을 차지한다.
• 즉, 문자열은 O(n)의 공간을 갖는다.

3. reference 타입

• 객체, 배열 등은 대부분 O(n)의 공간을 갖는다.

예시

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

// 두 개의 공간의 숫자를 저장, O(1) 공간

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

// 차지하는 공간은 arr의 크기와 비례해서 커진다, O(n)의 공간