[자료구조] 복잡도(시간, 공간, 빅오 표기법)

복잡도(Complexity)란?

복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도

복잡도는 크게 시간, 공간 복잡도로 나눌 수 있다.

 

시간 복잡도(Time Complexity)

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 시간이 얼마나 걸리는지를 의미
• 알고리즘을 위해 필요한 연산의 횟수

 

시간 복잡도의 3가지 케이스

1. 최선의 경우(Best Case)
   • 빅 오메가 표기법 사용
   • 최선의 시나리오로 최소 시간이 걸림
2. 평균적인 경우(Average Case)
   • 빅 세타 표기법 사용
   • 평균 시간을 나타냄
3. 최악의 경우(Worst Case)
   • 빅 오 표기법 사용 
   • 최악의 시나리오로 최대 시간이 걸림

알고리즘에서는 항상 최악의 상황을 고려해야 하기 때문에 최악의 경우로 알고리즘의 성능을 파악합니다. 

 

빅오 표기법

빅오 표기법	표현
O(1)	상수
O(logN)	로그
O(N)	선형
O(NlogN)	로그 선형
O(N^2)	다항
O(2^n)	지수

공간 복잡도(Space Complexity)

• 공간 복잡도는 알고리즘에서 사용되는 메모리의 양을 나타냄
• 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구 → S(P) = c + Sp(n)

※ 고정 공간 = 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)

※ 가변 공간 = 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출 할 경우 요구되는 추가 공간, 즉, 동적으로 필요한 공간

 

공간 복잡도 예시

가장 유명한 재귀함수인 팩토리얼을 예시로 들겠습니다. 

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

지금 재귀 함수로 스택에 n부터 1까지 모두 쌓이게 됩니다. 따라서 공간 복잡도는 O(n)입니다. 

 

팩토리얼(재귀 X, 반복문 사용)

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

n의 값에 상관없이 스택에는 n과 i 그리고 fac 변수만 저장됩니다. 여기서의 공간 복잡도는 O(1)입니다.