[컴퓨터 알고리즘 성능분석] 시간 복잡도 vs 공간 복잡도

[컴퓨터 알고리즘 성능분석] 시간 복잡도 vs 공간 복잡도

시간 복잡도와 공간 복잡도

알고리즘 트레이닝 사이트에서 문제를 풀다보면 아래 그림과 같이 시간 복잡도와 공간 복잡도가 조건으로 주어진다.

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

정의는 아래와 같다.

- 시간 복잡도(Time Complexity) : 알고리즘의 수행시간 분석결과

- 공간 복잡도(Space Complexity) : 알고리즘의 메모리 사용량에 대한 분석결과

간단하게 말하면 알고리즘 성능평가는 시간 복잡도와 공간 복잡도를 계산하고 점근적 표기법으로 나타내면 된다.

(점근적 표기법 포스팅 : http://ledgku.tistory.com/31)

시간 복잡도 계산법

알고리즘의 시간 복잡도는 연산의 횟수를 세고 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 만들면 된다. 알고리즘의 실행 시간을 재는 방법을 생각할 수도 있는데 이 방법을 객관성이 떨어진다.

순차 탐색 알고리즘으로 시간 복잡도를 구하는 연습을 해보자.

배열에 찾고 싶은 숫자를 처음부터 끝까지 찾고 찾는 숫자가 있으면 인덱스를 반환해 주는 알고리즘이다.

#include <stdio.h>
 
int LSearch(int ar[], int len, int target){
    int i = 0;
    for (; i < len; i++){
        if (ar[i] == target){
            return i;
        }
    }
    return -1;
}
 
int main(int arc, char** argv){
    int arr[] = { 3, 1, 8, 5, 6, 7, 2, 9, 4 };
    int idx = 0;
 
    idx = LSearch(arr, sizeof(arr) / sizeof(int), 10);
    if (idx == -1){
        printf("Fail!!\n");
    }
    else{
        printf("Target Index : %d\n", idx);
    }
 
    idx = LSearch(arr, sizeof(arr) / sizeof(int), 1);
    if (idx == -1){
        printf("Fail!!\n");
    }
    else{
        printf("Target Index : %d\n", idx);
    }
 
    return 0;
}

시간 복잡도를 계산하려면 연산의 횟수를 세라고 했다. 그럼 모든 연산의 횟수를 세야 하는가? 당연히 아니다. 알고리즘의 핵심이 되는 연산의 횟수만 세면 된다. 순차탐색 알고리즘에 핵심이 되는 연산은 == 연산이다. == 연산에 따라 다른 연산들은 많이 수행될 수도 있고 적게 수행될 수도 있는 종속적인 관계이기 때문이다.

연산의 횟수를 세어 보자.

만약 3을 찾는다면 1번만에 종료되는 최선의 경우(Best Case), 4를 찾는 다면 배열의 크기 n번만에 종료되는 최악의 경우(Worst Case), 그리고 평균적인 경우(Average Case)가 있다.

평균적인 경우가 가장 이상적으로 보이겠지만 알고리즘이 복잡해 질수록 평균적인 경우는 구하기가 매우 어려워 진다. 그러므로 최악의 경우로 알고리즘의 성능을 파악한다.

최악의 경우는 n번째에 데이터를 찾는 경우이므로 연산횟수는 n이다. 

$$ T(n) = n $$

빅오 표기법은 아래에서 설명하도록 하겠다.

공간 복잡도 계산법

공간 복잡도 계산은 간단하다. 메모리를 얼마나 사용하는지 계산하면 된다.

예를 들어 크기가 n인 배열을 입력했는데 알고리즘이 내부에서 n x n의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 $n^2$이 된다.

공간 복잡도는 보통 시간 복잡도에 밀려 중요하게 생각하지 않는 경우가 많은데 빅데이터 처리를 할 경우 공간 복잡도가 위와 같이 제곱으로 뛰게 되면 프로그램이 메모리에 한번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생한다.

그래서 빅데이터 처리시 데이터를 나눠서 처리하고 다시 합치는 방법을 사용하게 된다.

알고리즘 작성시 공간 복잡도를 아예 생각하지 않게 되면 문제가 발생할 수도 있으므로 공간 복잡도도 신경써서 작성하는게 좋다.

빅오 표기법

예를 먼저 보면,

$$ T(n) = n^2 + 2n + 9    ->    O(n^2) $$

$$ T(n) = n^4 + n^3 + n^2 + 1    ->    O(n^4) $$

$$ T(n) = 5n^3 + 3n^2 + 2n + 1    ->    O(n^3) $$

위 예와 같이 T(n)으로 표현한 함수의 최고차항의 차수가 빅오가 된다.

빅오의 순서는 아래와 같고 커질수록 좋지 않다.

보통 O(n^2)이상의 복잡도를 가지는 알고리즘은 좋지 않다.

$$ O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) < O(n!) $$

빅오를 이용한 성능 비교

n	$O(n) $	$O(logn) $
500	500	9
5,000	5,000	13
50,000	50,000	16

위 표를 통해 $O(n)$의 알고리즘과 $O(logn)$의 알고리즘이 연산횟수에 있어서 얼마나 많은 차이가 있는지 알 수 있다.