공간 복잡도, 시간 복잡도에 대해 알아보자 (feat. Big-O)

복잡도

- 알고리즘의 성능과 효율성을 나타내는 척도

- 크게 시간 복잡도와 공간 복잡도로 나눌 수 있음

- 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시

- 복잡도는 점근 표기법으로 나타내며, O(빅오), Ω(빅 오메가), Θ(빅 세타) 등으로 표현

> 주로 빅오와 세타 표기법이 많이 사용된다

 

 

 

 

 

시간 복잡도

알고리즘의 수행 시간을 평가

수행 시간은 실행 환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가

시간 복잡도는 다음 3가지 경우로 평가

 

- 최선의 경우 (Best Case)

빅 오메가 표기법 사용

최적의 입력을 한 상태에서 작업을 완료하는데 가장 연산 횟수가 적은 경우

 

- 최악의 경우 (Worst Case)

빅오 표기법 사용

최악의 입력을 한 상태에서 작업을 완료하는데 가장 연산 횟수가 많은 경우

알고리즘이 복잡해질 수록 평균적인 경우를 구하기 어렵기 때문에 최악의 경우로 알고리즘의 성능을 주로 파악

 

- 평균적인 경우 (Average Case)

빅 세타 표기법 사용

여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

 

 

 

 

 

시간 복잡도 계산

- O(1) 상수 시간

입력 크기에 상관없이 일정한 연산을 수행

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

위 알고리즘은 입력 크기에 상관없이 한 번만 연산을 수행하기 때문에 O(1)

 

- O(log N) 로그 시간

입력 크기가 커질 떄 연산 횟수가 logN에 비례하여 증가

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

이 경우 i 값이 반복때마다 2배씩 증가하기 때문에 LogN

 

- O(n) 선형 시간

입력 크기가 커질 때 연산 횟수가 크기에 비례하여 증가

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

위 알고리즘은 n만큼 반복문을 수행

n 값에 비례하여 연산수가 선형적으로 증가하기 대문에 O(n)

 

- O(n^2) 2차 시간

입력 크기가 커질 때 연산 횟수가 N^2에 비례하여 증가

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

 

위 알고리즘은 for문이 중첩되어 있기 때문에 n^2에 비례하여 연산수가 증가

 

- O(2^n) 지수 시간

입력 크기가 커질 때 연산 수가 2^n에 비례하여 증가

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

위 알고리즘은 피보나치 수를 구하는 알고리즘

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

 

 

 

 

 

공간 복잡도

알고리즘에서 사용하는 메모리의 양

보조 공간 (Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념

보조 공간은 알고리즘이 실행되는 동안 사용하는 임시공간으로 입력 공간을 고려하지 않는다

 

 

 

 

 

공간 복잡도 계산

시간 복잡도와 유사하게 빅오 표기법을 사용

 

int sum(int a[], int n)
{
  int x = 0;		
  for(int i = 0; i < n; i++) {
    x  = x + a[i];
  }
  return(x);
}

 

위 알고리즘은 4개의 변수를 사용

int a[n] = 4 * n byte (입력 공간)

int n = 4 byte (입력 공간)

int x = 4 byte (보조 공간)

int i = 4 byte (보조 공간)

총 4n+12 byte의 메모리를 요구 

입력 값에 따라 메모리의 사용량이 선형적으로 증가하기 때문에 공간 복잡도는 O(n)이 됨

 

 

 

 

 

 

 

Reference

복잡도(Complexity): 시간 복잡도와 공간 복잡도, 그리고 빅오(Big-O) 표기법

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)