[자료구조&알고리즘]Big O 표기법 (빅오) #3

빅오 표기법으로 표현한 알고리즘의 성능 간 그래프입니다.

(왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)

                                                           

 

( 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수 )

시간복잡성과 공간복잡성

알고리즘을 평가할 때 주로 수행 시간과 메모리 사용량을 기준으로 두는데, 이 중 수행 시간에 해당하는 것이 시간 복잡도이고 메모리 사용량에 해당하는 것이 공간 복잡도이다.

Big O의 시간 복잡성

시간 복잡도는 일반적으로 빅오 표기법으로 나타냅니다.

연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타냅니다.

 

예를 들어 입력 크기가 n이라고 했을 때 다음과 같이 표기합니다.

• T(n)=n2+2n+1=O(n2) : 최고차항만 나타냄.
• T(n)=2n=O(n) : 최고차항의 계수는 제외함.

O(1) - 상수 시간 (Constant time)

입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)입니다.

void func (int n) {
  printf("%d\n", n);
}

위 알고리즘은 n에 상관없이 한 번에 연산만 수행하기 때문에 시간 복잡도는 다음과 같습니다.

T(n)=O(1)

O(logN) - 로그 시간 (Logarithmic time)

입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)입니다.

for(i=1; i<=n; i*2) {
  ...
}

위 알고리즘은 i 값이 반복할 때마다 2배씩 증가합니다. 이것을 k번 반복했을 때 다음과 같습니다.

2k=N 이 되고 반복문이 종료됩니다. 양쪽에 로그를 취하면 다음과 같습니다.

log2(2k)=log2N

k=log2N

k는 수행 횟수이기 때문에 시간 복잡도는 다음과 같습니다.

T(n)=logN

O(n) - 선형 시간 (Linear time)

입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간 복잡도는 O(n)입니다.

• 연산횟수가 선형적으로 증가하는 형태

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

위 알고리즘은 n만큼 반복문을 수행합니다.

n에 값에 비례해서 연산수가 선형적으로 증가하기 때문에 시간 복잡도는 다음과 같습니다.

T(n)=O(n)

O(n2) - 2차 시간 (Quadratic time)

입력 크기(n)가 커질 때 연산 횟수가 n2에 비례해서 증가하면 시간 복잡도는 O(n2)입니다.

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

위 알고리즘은 for문이 중첩되어 있기 때문에 n2에 비례해서 연산수가 증가합니다.

시간 복잡도는 다음과 같습니다.

T(n)=O(n2)

O(2n) - 지수 시간 (Exponential time)

입력 크기가 커질 때 연산수가 2n에 비례해서 증가하면 시간 복잡도는 O(2n)입니다.

int func (int n) {
  if (n <= 1) 
    return n;
  return func(n-1) + fun(n-2);
}

위 알고리즘은 피보나치 수를 구하는 알고리즘입니다.

한번 함수를 호출할 때마다 두 번씩 재귀로 함수를 호출하기 때문에 2n에 비례해서 연산수가 증가합니다.

시간 복잡도는 다음과 같습니다.

T(n)=O(2n)

---

 

<예제>

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

 

-시간 복잡도

위예제를 시간복잡도의 관점에서 봤을 때, for 문으로 인한 루프 그리고 해당 for문은 입력값인 arr 의 길이(n)에 따라 변화하므로 O(n) 이라고 할 수 있다.

-공간 복잡도

위 예제를 공간복잡도의 초점에서 공간(메모리)를 차지하는 영억은 어디가 해당되는 것인가를 살펴보는 것이 중요하다.

1. 먼저, sumA() 는 total = 0 에서 변수 total에 상수 0을 할당한다.(메모리를 차지한다.)
2. 두번째로 for문 내에 let i = 0 에서 변수 i에 상수 0을 할당한다.(메모리를 차지한다.)

입력인 arr 의 길이에 따라 시간 복잡도는 변화할 수 있겠으나 sumA() 함수 내에 메모리를 할당하여 차지하게 되는 영역은 2가지에 불과하며 return 되는 값 total은 결국 상수(number) 이다.

JS에서의 공간 복잡도 규칙에서 보았듯 number 의 공간복잡도는 일정하다. 즉 O(n) 이다.

<예제2>

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

-시간 복잡도

시간 복잡도의 관점에서 입력되는 값 arr의 길이에 따라 for 문의 루프 길이가 변화게 되고 이는 곧 O(n) 을 의미한다.

-공간 복잡도

sumA() 함수의 공간 복잡도와 동일하게 공간(메모리)을 차지하는 영역을 살펴본다.

1. let newArr = []; 에서 배열이 변수 newArr 에 할당된다.
2. for 문 내에서 let i = 0; 으로 변수 i에 0이 할당된다.
3. for 문 내에서 변수 newArr 이 입력 값인 arr 의 길이에 따라 비례하여 반복실행되며 newArr에 push 되어 메모리의 크기가 커진다.

1.~2.를 통해서 +2가 되며, 3. 에서 입력 값인 배열 arr의 길이에 따라 newArr의 공간의 크기가 비례하여 변화하는 것에 따라, n+2 임을 알 수 있다.

즉, 빅오 표현식의 단순화에 따라 O(n) 이다.