알고리즘의 복잡도란? (1. 공간 복잡도)

복잡도가 낮을 수록 성능이 뛰어난 알고리즘입니다.

알고리즘의 복잡도(Complexity)는 두 가지 요소로 측정합니다.

1. 공간 복잡도 (Space complexity)

간단합니다. 사용되는 변수의 개수를 의미합니다.

단, 인자 변수들은 일반적으로 제외하고 카운트합니다.

예를들어 아래와 같은 함수의 경우, 공간 복잡도는 "2" 입니다. (sum, i)

(함수 내용은 이해할 필요 없음)

public int solution(int n) {
    int sum = 0;
 
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
 
    return sum;
}

또 하나의 예시를 들어보면, 아래 함수의 경우 공간 복잡도는 "N + 3" 입니다. (counter, tmpMaxCounter, doneMaxCounter, i)

(마찬가지로 함수 내용은 이해할 필요 없음)

public int[] solution(int N, int[] A) {
    int[] counter = new int[N];
    int tmpMaxCounter = 0;
    int doneMaxCounter = 0;
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] > N) {
            doneMaxCounter = tmpMaxCounter;
        }
        else {
            if (counter[A[i] - 1] < doneMaxCounter) {
                counter[A[i] - 1] = doneMaxCounter;
            }
 
            counter[A[i] - 1]++;
 
            if (counter[A[i] - 1] > tmpMaxCounter) {
                tmpMaxCounter = counter[A[i] - 1];
            }
        }
    }
 
    if (doneMaxCounter > 0) {
        for (int i = 0; i < counter.length; i++) {
            if (counter[i] < doneMaxCounter) {
                counter[i] = doneMaxCounter;
            }
        }
    }
 
    return counter;
}

2. 시간 복잡도 (Time complexity)

다음 글에..

3. 빅오 표기법 (Big-O notation)

다음 다음 글에..