알고리즘의 복잡도란? (2. 시간 복잡도)

1. 공간 복잡도 (Space complexity)

이전 글에..

2. 시간 복잡도 (Time complexity)

반복문을 총 몇번 도는지를 의미합니다.

아래는 1부터 n까지의 합을 구하는 함수입니다.

시간 복잡도는 "n" 입니다.

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

같은 함수를 수학공식을 이용해 아래와 같이 바꾸면 시간 복잡도는 "1" 이 됩니다.

(수학을 잘하면 알고리즘에 유리합니다)

public int solution(int n) { 
    return (1 + n) * n / 2;
}

API 사용시에는 주의해야합니다.

아래 함수의 시간 복잡도는 얼마일까요? "A.length" 일까요?

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

public int solution(int[] A) {
    List<Integer> marks = new ArrayList<>();
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] > A.length) {
            return 0;
        }
 
        if (marks.contains(A[i])) {
            return 0;
        }
 
        marks.add(A[i]);
    }
 
    return 1;
}

답은 "A.length X A.length" 입니다. "A.length" 의 제곱이지요.

왜냐하면 ArrayList.contains() 함수의 시간 복잡도가 "해당 list의 길이" 이기 때문입니다.

(내부적으로 list 전체를 반복문을 돌면서 인자로 던져준 객체가 있는지 확인합니다)

위 함수에서 ArrayList 대신 HashSet 을 사용하면 어떨까요?

출력은 같지만 복잡도는 "A.length" 가 됩니다.

HashSet.contains() 함수의 시간 복잡도는 "1" 이기 때문입니다.

public int solution(int[] A) {
    Set<Integer> marks = new HashSet<>();
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] > A.length) {
            return 0;
        }
 
        if (marks.contains(A[i])) {
            return 0;
        }
 
        marks.add(A[i]);
    }
 
    return 1;
}

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

다음 글에..