1.1Big O Notation

'더 좋은' 알고리즘의 기준

문제를 해결하는 방법은 여러가지가 있다. 그 중 어떤 것이 가장 좋은 알고리즘일까?

• 더 빠른 방법?
• 메모리를 덜 쓰는 방법?
• 코드가 더 읽기 쉬운 방법?

... 물론 상황에 따라 다르다.

그러면 좀 더 와닿게, 예시로 살펴보자. 1부터 n까지의 숫자를 다 더하는 함수를 만든다고 해보자. 가장 직관적인 방법은 아래의 방법일 것이다.

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

"다른 방법이 있나?"라고 질문할 수도 있겠지만, 있다. 수학시간에 배운 가우스의 공식을 기억한다면 다음과 같이 구현할 수도 있다:

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

어떤게 더 나은 방법일까? 직접 시간을 재보자.

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

시간을 재보면, 유의미하게 후자가 더 낫긴 하다. 하지만 이렇게 측정하는게 확실히 우열을 가리기 좋은 방법일까? 같은 컴퓨터로 같은 환경에서 여러번 실행해도 계속 결과값이 바뀐다. 또, 입력값이 바뀌어도 성능 차이가 같을지 확신할 수가 없다.

우리는 더 안정적인 기준이 필요하다. 알고리즘이 특정 문제를 푼 시간을 재기보다는 컴퓨터가 수행해야 하는 기본 연산의 수를 비교하는게 보다 안정적이다. 예를 들어, n * (n + 1) / 2는 처음에 덧셈 한번, 이후에 n과의 곱셈 한번, 그리고 마지막으로 2를 나누는 3번의 연산을 수행한다. n이 아무리 커져도 3번의 연산이라는 사실은 변하지 않는다.

하지만, for문을 사용한 경우는 다르다. 덧셈을 n번 수행하는데다가, 할당(assignment), 즉 total이라는 변수에 누계를 계속 할당하는 연산도 n번 수행하기 때문에 n에 비례한 수의 연산을 수행한다.

심지어 자세히 보면 맨 처음에도 total에 0을 할당하고, for문도 계속 비교 연산을 수행한다. 실제 연산 수는 더 많다는 것이다.

Big O Notation

Big O 표기법은 알고리즘이 입력값 크기 n에 따라 얼마나 많은 연산을 수행하는지, 즉 시간 복잡도나 공간 복잡도를 추상적으로 표현하는 방법이다.

다음은 대표적인 Big O 표현들이다:

• O(1) — 상수 시간(constant)
• O(log n) — 로그 시간(logarithm)
• O(n) — 선형 시간(linear)
• O(n log n) — 선형로그 시간(linear-logarithm)
• O(n²), O(n³) 등 — 다항 시간(polynomial)
• O(2ⁿ) — 지수 시간(exponential)
• O(n!) — 팩토리얼 시간(factorial)

예를 들어, 우리가 살펴본 두 개의 addUpTo(n) 함수 중,

• 가우스의 방법은 항상 세 번의 연산을 하는 상수 연산이므로 O(1)
• for 루프문으로 다 더하는 방식은 n에 비례한 반복을 하므로 O(n)

Big O 표현 단순화 규칙

1. 상수는 무시한다: O(2n) 등 계수를 붙여 쓰지 않고, 다 O(n)으로 쓴다. 마찬가지로, 상수일 경우도 O(500)이라고 쓰지 않고 O(1)이라고 쓴다.
2. 작은 지수 항은 무시한다: O(n + 10), O(1000n + 50) 등도 모두 O(n)으로 쓴다.

자주 등장하는 Big O 패턴들

• 기본 산술 연산은 O(1)
• 변수에 값을 할당하는 것도 O(1)
• 배열의 인덱스로 접근하거나 객체에서 키로 값을 가져오는 것도 O(1)
• 루프 내부에서 수행하는 연산이 O(1)이라면, 반복 횟수에 따라 전체 복잡도는 O(n)

이미지 출처 : #

Space Complexity (공간 복잡도)

지금까지는 알고리즘의 시간의 복잡도(Time Complexity)에 대해 알아보았다. 이번에는 공간, 즉 메모리 사용량 기준으로 성능을 살펴보자.

JavaScript 기준, 아래는 공간 복잡도와 관련된 일반적인 규칙들이다:

• 대부분의 원시 타입(Primitive Value), 즉 boolean, number, undefined, null은 O(1)
• 문자열(string)은 O(n)
• 참조 타입(Reference Type), 즉 배열이나 객체(array, object)는 일반적으로 O(n)

시간 복잡도와 공간 복잡도는 어떻게 다를까? 배열 안의 모든 수를 더하는 아래의 함수를 보자.

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

이 함수는 입력값의 배열이 아주 길어지더라도 사용하는 변수는 total과 i, 총 두 개 뿐이다. 배열의 길이만큼 값을 읽지만, 그렇다고 추가적인 메모리를 사용하진 않기 때문에 공간 복잡도는 O(1)이다.