• https://madplay.github.io/post/time-complexity-space-complexity

시간복잡도, 공간복잡도

시간복잡도

알고리즘의 절대적 실행시간을 나타내지 않는다.
알고리즘을 수행하는데 이뤄지는 연산을 숫자로 표기하는 것이다.
(연산에는 산술, 대입, 비교, 이동 연산이 있다.)
연산의 실행 횟수는 입력한 데이터 n에 따라 변하게 된다.
수식으로는 T(n)으로 표기한다.

빅오 표기법

시간 복잡도 함수에서 상대적으로 불필요한 연산을 제거하여
알고리즘 분석을 조금 간편하게 할 목적으로 시간복잡도를 표기하는 방법

연산 횟수가 8n^2 + 2 일 때, 빅오 표기법을 적용한 시간복잡도는 O(n^2) (빅오 of n^2) 이라고 한다.

최선, 평균, 최악의 경우

최선 : 실행시간이 가장 적은 경우
평균 : 모든 입력을 고려하고, 각 입력이 발생할 확률을 고려한 평균 수행 시간
최악 : 알고리즘의 수행시간 중 가장 오래 걸리는 경우

배열에서 원소를 찾는 경우
최선 : O(1) 배열의 0번째 인덱스에 원소가 있는 경우
최악 : O(n) 배열의 마지막 인덱스에 원소가 있는 경우

공간복잡도

프로그램을 실행시킨뒤 완료하는데 필요한 자원 공간의 양
총 공간 요구 = 고정 공간 요구 + 가변 공간 요구
고정 공간 : 입력,출력의 횟수나 크기에 관계없는 공간의 요구
(코드 저장공간, 단순 변수, 고정 크기 구조 변수, 상수)
가변 공간 : 특정 인스턴스에 의존하는 크기를 가진 구조화 변수
(동적으로 필요한 공간)

공간복잡도 예시

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

n이 1이하일 때까지 함수가 재귀적으로 호출되어 스택에 n~1까지 쌓인다
=> 공간 복잡도 O(n)

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)