알고리즘의 복잡도란? (3. 빅오 표기법)

1. 공간 복잡도 (Space complexity)

이전 이전 글에..

2. 시간 복잡도 (Time complexity)

이전 글에..

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

복잡도를 표현하는 단위입니다.

거리의 단위에 km 가 있고, 무게의 단위에 kg 이 있듯

복잡도의 단위로는 O 가 있습니다.

공간 복잡도와 시간 복잡도 둘 다에 사용되며

최악의 경우를 가정하여 나타냅니다.

최악이 무슨 말인지 아래 예시를 보여드리겠습니다.

public boolean contains(int[] arr, int num) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == num) {
            return true;
        }
    }
 
    return false;
}

위 함수의 경우, 운이 좋으면 한번만에 찾아서 return true가 될 수도 있고,

운이 최악이면 arr 전체를 다 뒤져야할수도 있습니다.

Big-O 는 이 최악을 가정하여 나타내므로

O(n) 이 위 함수의 시간 복잡도입니다.

n 은 뭐냐면 입력받은 배열의 길이를 뜻합니다.

또 특이한 점은 상수는 간소화한다는 것입니다.

O(k * 1)  =>  O(1)

O(k * n)  =>  O(n)

O(n + k)  =>  O(n)

O(k * n제곱)  =>  O(n제곱)

아래 함수를 예로 들겠습니다. (함수 내용 이해할 필요 없음)

시간 복잡도는 "2n + 2" 이지만 (n + n + 2)

Big-O 표기법으로는 O(n) 입니다.

공간 복잡도는 "n + 3" 이지만 (checked, i  =>  n + 2 + 1)

Big-O 표기법으로는 O(n) 입니다.

public int solution(int[] A) {
    boolean[] checked = new boolean[A.length + 2];
 
    for (int i = 0; i < A.length; i++) {
        checked[A[i]] = true;
    }
 
    for (int i = 1; i < checked.length; i++) {
        if (!checked[i]) {
            return i;
        }
    }
 
    return -1;
}