시간복잡도와 공간복잡도

Algorithm

마닐라 2022. 3. 28. 13:21

시간복잡도란 알고리즘을 수행하는 데에 연산들이 몇 번 이루어지는지 표기하는 것입니다.

알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어렵기에 시간복잡도의 척도를 계산할 때는 최악의 경우(빅 오 표기법)를 주로 사용합니다.

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

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

O(logN) - 연산횟수가 logN에 비례해서 증가하면 시간복잡도는 O(logN)입니다.(이진 탐색)

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

O(n) - 연산횟수가 n에 비례해서 증가하면 시간복잡도는 O(n)입니다.

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

O(n^2) - 연산횟수가 n^2에 비례해서 증가하면 시간복잡도는 O(n^2)입니다.

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

O(2^n) - 연산횟수가 2^n에 비례해서 증가하면 시간복잡도는 O(2^n)입니다.

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

공간복잡도란 프로그램을 실행시킨 후 완료하는 데에 필요한 자원 공간의 양(메모리 공간)을 말합니다.

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

고정 공간은 입력과 출력의 횟수나 크기와 관계 없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말합니다.

가변 공간은 동적으로 필요한 공간을 말합니다.

다음 메서드의 공간복잡도를 계산해보겠습니다.

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

위 알고리즘은 4개의 변수를 사용하고 있습니다.

총 4n+12의 메모리를 요구하고 빅오 표기법에 따라 공간 복잡도는 O(n)이 됩니다.

O(1) - 일반적으로 공간이 하나씩 생성되는 것을 1이라고 표현합니다.

int a = 10;

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

위의 메서드에서 반복문이 n까지 반복되더라도 i와 result 변수만 사용합니다. 공간복잡도는 O(1) 입니다.

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

위의 메서드는 n의 값에 따라서 공간복잡도가 달라지게 됩니다.

n부터 1까지 메서드가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이게 됩니다. 공간복잡도는 O(n)이 됩니다.

공간복잡도 계산1

float abc(float a, float b, float c) {
   return(a + b + b*c + (a + b - c)/(a + b) + 4.0);
}

위의 메서드를 보면 변수 a, b, c는 함수 내에서 해결하고자 하는 문제와는 무관합니다.

따라서 공간복잡도는 0입니다.

공간복잡도 계산2

float Sum(float a[], int n) {
	float s = 0.0;
	for(int i = 1; i < = n; i++) s += a[i];
 	return s;
}

위의 메서드에서 사용되는 변수는 a[], n, s, i 입니다. 1번과는 다르게 변수 a[]는 합을 구하기 위해서 반복문 내에서 n개의 원소가 모두 참조되고 있습니다. 그리고 n은 for문을 벗어나기 위한 한계값으로 사용되고 있습니다.

위의 메서드의 공간 복잡도는 (a[]를 저장하기 위한 공간) + 변수 n, s, i를 위한 공간) = O(n+3)이 됩니다.

공간복잡도 계산3

float RSum(float a[], int n) {
	if(n <= 0)
   	return (0.0);
 	else
   	return (RSum(a, n-1) + a[n]);
}

위의 경우에는 사용되는 변수는 a[], n이고 n은 if문 내에서 순환의 한계값으로 사용되고 있습니다.

또한 변수 a[]는 합을 구하기 위해 사용되고 있으며 a[]의 원소중 n번째의 원소만 필요로 합니다.

위의 메서드의 공간 복잡도는 (a[]의 n번째 원소를 위한 공간) + (n을 위한 공간) = 1 + 1입니다.

하지만 해당 메서드는 재귀의 형태로 작성되었습니다.

그렇기 때문에 몇 번의 재귀가 뻗어나가는지와 메서드의 복귀 주소를 저장할 공간도 추가가 되어야 합니다.

위의 함수는 n부터 0까지 재귀가 뻗어 나가므로 재귀의 깊이는 n+1 입니다.

따라서 공간복잡도는 재귀 깊이 X (a[n], n, 메서드의 복귀 주소) = O(3*(n+1)) 이 됩니다.

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 동적 할당을 한다면 얼마만큼의 동적 할당이 예상되는지, 재귀 함수라면 재귀 호출을 몇번이나 하는지 등이 공간 복잡도에 영향을 미칩니다.

함수 호출 시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다.

특히 재귀 함수같은 경우는 매 함수마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요하기 때문에 재귀적으로도 반복문으로도 짤 수 있는 코드라면 반복문이 효율성이 높다고 볼 수 있습니다.

참고