Computer Science/Algorithm

시간복잡도와 공간복잡도

비소_ 2022. 5. 25.

알고리즘 성능 분석

프로그램 규모가 커짐에 따라 처리해야 하는 데이터 양도 많아지고 있다.

따라서 효율적인 알고리즘을 통해 문제를 해결하는 것은 매우 중요한 일이다.

그러면 어떻게 효율적인지 알 수 있단 걸까?

이를 분석하기 위해 일반적으로 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 이용한다.

시간 복잡도

우리의 컴퓨터가 연산 1회를 처리하는데 1초가 걸린다고 가정해보자.

그러면 당연히 같은 입력 데이터가 주어졌을 때 연산 횟수가 최소인 알고리즘을 사용해야 빠르게 처리할 수 있을 것이다.

결국 우리는 알고리즘이 몇 번 연산을 수행하는지 셀 수만 있으면 된다.

아래는 n의 제곱을 1씩 n*n번 더해서 구하는 함수이다.

int func (int n) {
    int sum = 0; //대입 1회

    for(i = 0; i < n; i++) { //증감연산자는 i = i + 1이다
    	for(int j = 0; j < n; j++)
    		sum++;            
    }
    return sum;
}

연산	횟수
대입	$2 * (n * n) + n + 1$
덧셈	$2 * (n * n) + n$
합	$4n^2 + 2n + 1$

우선 대입의 경우, sum = 0에서 1회, i에서 n회, j에서 n * n회, sum에서 n * n회 발생한다.

덧셈도 sum = 0을 제외하고는 이와 동일하다.

이를 시간 복잡도 함수 표기법인 T(n)으로 표기하면 $T(n) = 4n^2 + 2n + 1$이다.

하지만, 이렇게 짧고 간단한 코드도 일일이 연산 횟수를 세고 있자니 답답한 노릇이다.

따라서, 빅-오 표기법(Big-O Notation)을 사용하여 이를 간단히 한다.

빅-오 표기법

빅오 표기법(Big-O Notation)이란, 시간 복잡도 함수에서 상대적으로 불필요한 연산을 제거하여 시간 복잡도를 표기하는 방법이다.

이것이 가능한 이유는 입력 크기(n)가 커질수록 차수가 높은 항의 영향력이 커지기 때문이다.

아래 역시 최고차항($n^2$)으로 인해 횟수가 급격히 늘었지만, n과 상수는 영향력이 굉장히 적다.

입력 크기(n)	연산 횟수(T(n))
n = 10	4 * 10 * 10 + 2 * 10 + 1 = 421
n = 100	4 * 100 * 100 + 2 * 100 + 1 = 40201

다른 알고리즘과도 비교해보자.

입력 크기(n)	$T(n) = 4n^2 + 2n + 1$	$T(n) = 2n^2 + 100$	$T(n) = 30n$
n = 10	421	300	300
n = 100	40,201	20,100	3,000
n = 1000	4,002,001	2,000,100	30,000

최고차항의 차수가 동일하다면 그 계수에 영향을 받을 수는 있겠지만, 더 낮은 차수의 알고리즘이 있다면 계수는 일반적으로 의미가 없어진다.

(하지만, 종종 계수의 차이가 너무 많이 나서 역전되는 상황이 일어난다.)

따라서, 가장 영향력 있는 항만 남기고 나머지 항을 제외해서 표기하는 방법이 빅오 표기법이다.

$T(n) = 4n^2 + 2n + 1 : O(n^2)$
$T(n) = 2n^2 + 100 : O(n^2)$
$T(n) = 30n : O(n)$

계수까지 제외하는 이유는 일반적으로 n이 무한대로 발산할 경우, 이에 곱해지는 상수는 무시되기 때문이다.

(수학에서 무한(INF) * 상수(c) = 무한(INF)인 이유와 같다. 현실에서는 데이터가 유한하므로 계수를 결코 무시할 순 없다.)

빅오 표기법을 이용하면 n에 얼마나 비례하는지 알 수 있어 직관적이다.

많이 쓰이는 빅 표기법은 아래와 같다.

빅오 표기법	n = 1	n = 4	n = 8	n = 32
$O(1)$	1	1	1	1
$O(log n)$	0	2	3	5
$O(n)$	1	4	8	32
$O(n log n)$	2	8	24	160
$O(n^2)$	1	16	64	1,024
$O(n^3)$	1	64	512	32,768
$O(2^n)$	2	16	256	4,294,967,296
$O(n!)$	1	24	40,326	26,313 $\times\ 10^{33}$

빅오 표기법을 이용하면 일일이 연산횟수를 세는 것이 아니라 n을 기준으로 전체적인 연산이 얼마나 반복되는지만 판단하면 된다.

(함수 안에 특별히 사용되는 함수(n과 연관된)가 없다면 중첩 반복문 수, 반복문 조건 등을 통해 쉽게 판단할 수 있다.)

코딩 테스트처럼 입력 크기와 제한 시간 등이 주어지는 상황에서는 본인이 어느 정도의 효율을 가지는 알고리즘을 작성해야 하는지 감잡을 수도 있다.

공간 복잡도

공간 복잡도(Space Complexity)란, 프로그램을 실행시킨 후 완료하는 데까지 필요한 자원 공간의 양(메모리)을 의미한다.

총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며, 수식으로는 $S(P)=c+S_P(n)$으로 표기한다.

여기서 고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말하며, 가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간을 말한다.

아래의 코드는 $n!$를 계산하는 재귀함수이다.

int factorial(int n)
{
    if(n > 1) return n * factorial(n - 1);
    else return 1;
}

n이 1 이하일 때까지 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이게 된다.

즉, 공간 복잡도는 $O (n)$ 이 된다.

아래와 같이 반복문으로 구현했을 경우, 공간 복잡도는 n과 상관없이 n, i, fac 변수만 저장되므로, O(1)이다.

int factorial(int n)
{
    int i = 0;
    int fac = 1;
    for(i = 1; i <= n; i++)
    {
        fac = fac * i;
    }
    return fac;
}

일반적으로 공간복잡도는 시간복잡도와 반비례하는데, 시간복잡도를 성능의 척도로 보는 경향이 많다.

최선, 평균, 최악의 경우

동일한 알고리즘도 입력 데이터에 따라 다른 결과를 나타낸다.

그래서 알고리즘의 효율성은 입력되는 데이터의 집합에 따라 3가지의 경우로 나누어 평가할 수 있다.
최선의 경우(Best Case) : 실행 시간이 가장 적은 경우
평균적인 경우(Average Case) : 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균 수행 시간
최악의 경우(Worst case) : 알고리즘의 수행 시간이 가장 오래 걸리는 경우

평균적인 경우로 성능을 판단하는 것이 가장 적절해 보이지만, 모든 입력데이터를 고려하는 것은 쉬운 일이 아니다.

따라서, 주로 최악의 경우를 기준으로 알고리즘을 판단한다.

일반적으로 최악의 경우에도 좋은 성능을 보여주는 알고리즘이라면 최선/평균의 경우에도 좋은 성능을 보이기 때문이다.