복잡도 - 시간복잡도

복잡도란?

복잡도는 우리가 정의한 알고리즘(로직, 함수 등)이 입력값에 대한 연산을 수행하는데 있어서

걸리는 시간, 차지하는 공간 에 대한 상관관계를 나타낸 것으로시간복잡도 와 공간복잡도 로 나누게 된다.

 

시간복잡도 - 표기

일반적으로 시간복잡도를 표기할 때에는

점근표기법중 하나인 대문자O표기법 (Big-O Notation)이 사용된다.

- $O(1)$, $O(n)$ 등 으로 표기한다.

 

표기할때에 유의 할 점은 최고차항을 제외한 모든 항과, 최고차항의 계수는 무시한다.

    예를들어 함수가 n개의 요소에 대한 연산을 처리할때에 걸리는 연산횟수가
    $4n^2+2n+1000$ 와 같다면 이에 대한 시간복잡도는 $O(n^2)$으로 표현한다.

 

아래는 모두 같은기능 (0부터 n까지(n을 포함)를 더한 값을 돌려주는)을 하는 함수이다.

// ver.1
function sum0toN(n) {
    let result = 0;
  for(i = 1; i <= n; i++){
      result = result + i;
  }
  return result;
}

 

// ver.2
function sum0toN(n) {
    return n === 1 ? 1 : n + sum(n - 1)
}

 

// ver.3
function sum0toN(n) {
    return (n + 1) * Math.floor(n / 2) + (n / 2 - Math.floor(n / 2)) * (n + 1)
}

각각의 버전을 시간복잡도로 나타내보면 다음과 같다.

    (1, 2, ... 숫자는 ver.1 , ver.2, ... 을 의미한다)

 

1. n의 숫자에 따라 n회 반복한다. → $O(n)$
2. n의 숫자에 따라 n회 재귀호출 한다. → $O(n)$
3. n의 숫자가 무엇이 오더라도 return구문의 연산과정만을 거친다.
   → $O(1)$

 

이처럼 매우 동일한 기능을 하는 알고리즘(로직, 함수)를 작성하더라도

어떻게 작성했느냐 에 따라서 시간복잡도의 형태가 달라지고

n값이 커질수록 형태에 따른 소요시간은 매우크게 차이나게 된다.

 

n 증가에 따른 시간복잡도별 연산횟수

 

여담이지만 ver.2의 경우 call stack에 대한 공간복잡도가 $O(n)$이기 때문에

n의 크기가 일정이상 커질경우 javascript에선 다음과 같은 오류를 출력한다.

Uncaught RangeError: Maximum call stack size exceeded