[Algorithm] 공간복잡도와 시간복잡도

 

공간복잡도란?

공간복잡도(Space Complexity)란 프로그램이 실행되고 완료되기까지 필요한 저장공간(memory)의 양을 말한다. 필요한 저장공간은 고정공간과 가변공간으로 나뉜다. 컴퓨터의 성능이 발전하면서 공간복잡도의 중요도는 점차 줄어들고 있다. 그래서 최근에는 시간복잡도를 더 우선하여 프로그래밍을 한다.

고정공간
알고리즘의 실행에 독립적인 공간이다. 단순하게 변수나 상수등 코드를 저장하는 공간이다.

가변공간
알고리즘의 실행에 의존적인 공간이다. 문제를 해결하려는 과정에서 동적으로 필요한 공간이다. 

S(P) = c + S𝚙(N)
c : 고정공간
S𝚙(N) : 가변공간​

고정공간 c는 상수이므로 공간복잡도는 가변공간의 크기에 좌우된다.

공간복잡도 계산법 - 빅-오(Big-O)

// 1
int x = 0;

// 2
public int getSumOneToN(int n) {
  int result = 0;
  for (int i = 1; i <= n; i++) {
    result += i;
  }
  return result;
}

일반적으로 위의 1번처럼 공간이 하나 생기는 것을 1이라 표현하고 공간복잡도는 O(1)이다. 2번처럼 반복문을 돌린다 해도 for문 안에서의 지역변수이기 때문에  2번의 공간복잡도도 O(1)이다.

// 1
public int getFactorial(int n) {
  if (n == 1) {
    return 1;
  }
  return n * getFactorial(n - 1);
}

// 2
public int sum(int[] arr) {
  int result = 0;
  for (int i = 0; i < arr.length; i++) {
    result += arr[i];
  }
  return result;
}

위의 1번 2번의 공간복잡도는 O(n)이다. 1번의 경우 함수가 n번호출 되어 스택에 1부터 n까지 쌓이게 되고 변수 n개가 만들어진다. 2번도 똑같다. 배열의 길이만큼 배열의 원소를 저장할 공간이 필요하다.

 

시간복잡도란?

시간복잡도(Time Complexity)는 알고리즘이 문제를 해결하기 위해 연산이 몇번 이루어지는지를 말한다. 여기서 말하는 연산은 보통 산술, 대입, 비교, 이동을 말한다.

알고리즘이 복잡해질수록 평균적인 경우(Average Case)가 나오는 경우가 드물기 때문에 알고리즘의 성능을 파악할 때는 최악의 경우(Worst Case)로 판단한다. 이렇게 최악의 경우를 계산하는 방식을 빅-오(Big-O)표기법이라 부른다.

O(1) (Constant)
프로그램에서 1라인이 실행되는 경우를 1이라 표현한다.

if (number % 2 == 1) {
  System.out.println("홀수");
} else {
  System.out.println("짝수");
}​

O(n) (Linear)
입력 데이터의 크기에 비례하여 처리시간이 증가하는 경우, 1차원 반복문

for (int i = 0; i < n; i++) {
  System.out.println(i);
}​

O(logn) (Logarithmic)
입력 데이터의 크기가 커질수록 처리시간이 로그만큼 짧아지는 알고리즘이다. 이진탐색이 대표적이다.

public static int binarySeacrh(int[] num, int target, int low, int high) {
    int mid = (low + high) / 2;
		
    if(target == num[mid]) {
      return mid;
    } else if(target < num[mid]) {
      return binarySeacrh(num, target, low, mid-1);
    } else {
      return binarySeacrh(num, target, mid+1, high);
    }
}​

O(n²) (quadratic)
데이터가 많아질수록 처리시간이 급수적으로 늘어난다. 2차원 반복문

for(int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    System.out.println(i * j);
  }
}​

O(2ⁿ) (Exponential)
데이터가 많아질수록 처리시간이 기하급수적으로 늘어난다. 피보나치 수열

public static int fibonacci(int n) {
  if (n == 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}​

O(nlogn) (Linear-Logarithmic)
데이터가 많아질수록 처리시간이 로그 배만큼 더 늘어나는 알고리즘. 병합정렬, 퀵정렬