시간 복잡도 계산하는 방법

date

Aug 1, 2023

slug

how-to-calcul-timecomplex

author

status

Public

좋은 알고리즘은 무엇일까?

개발자는 좋은 알고리즘을 만들어야 하는 숙명을 가지고 있습니다.

같은 기능 이라도, 좋은 알고리즘을 만드는 것이 더 메모리 사용량이 적거나 혹은 속도가 더 빠르기 때문입니다.

방금 말했듯이, 우리는 알고리즘의 성능 척도를 메모리를 얼마나 사용하느냐, 속도가 얼마나 빠르냐 등으로 나타냅니다.

사용자의 요구에 따라 다르지만, 일반적으로 우리는 알고리즘의 실행 속도를 성능의 척도로 계산하는데요, 이 기준을 시간 복잡도 라고 부릅니다.

시간 복잡도는 어떻게 구할까?

우리가 어떤 코드를 실행시켰는데, A가 구현한 코드는 실행이 5초가 걸리고, B가 구현한 코드는 실행이 3초가 걸렸습니다.

그렇다면 B가 구현한 코드가 A가 구현한 코드보다 좋은 알고리즘을 가지고 있는걸까요?

여기서 우리가 간과한 것은 우리가 같은 코드를 실행시키더라도 코드가 실행되는 환경이 모두 다르다는 사실입니다.

코드의 실행시간에는 컴퓨터의 성능 등의 요소가 많이 미치므로 우리는 코드가 실행되는 절대적인 시간이 아닌, 반복문과 같이 코드에 많은 영향을 미치는 부분을 기준으로 코드의 실행시간을 예측합니다.

먼저 간단한 알고리즘 문제를 함께 풀어보고, 코드의 실행시간을 함께 예측해봅시다.

주어진 정수 배열 중 음수가 있다면 그 음수를 반환하는 함수를 작성해야 합니다. (음수가 2개 이상인 경우, 가장 앞에 있는 음수를 return 합니다).

자바 코드로 풀이를 작성해보면 다음과 같습니다.


public int solution(int[] array) {
    for(int i = 0; i < array.length; i++) {
        if(array[i] < 0) return array[i]
    }
    return 0;
}

이 경우 array의 크기에 따라 반복속도가 달라지겠고, 또 주어진 array가

{-5, 2, 3, 7, 10} 일 때는 반복 없이 바로 코드가 종료됩니다.

{2, 3, -5, 7, 10} 일 때는 3번째 반복에서 코드가 종료됩니다.

{2, 3, 7, 10, -5} 일 때는 마지막 반복에서 코드가 종료됩니다.

위의 경우에서 처럼 어떤 배열이 주어지냐에 따라 최선의 경우 한 번만에 종료되기도 하고, 배열의 길이만큼 반복을 다 하고나서야 종료되는 경우도 있습니다.

따라서 이러한 경우에 따라 나뉘는 것처럼 성능 평가의 척도도 나뉘게 됩니다.

최선의 경우를 나타내는 경우 Big-Ω 로 나타냅니다.

최악의 경우를 나타내는 경우 Big-O (점근 표기법) 로 나타냅니다.

평균의 경우를 나타내는 경우 Big-Θ 로 나타냅니다.

그리고 일반적으로 우리는 성능을 평가 할 때, 최악의 경우를 산정하여 평가하는 Big-O 를 사용합니다.

따라서 위에 구현한 알고리즘은 최악의 경우 배열의 길이인 n번 만큼 실행됩니다.

우리는 그래서 시간 복잡도를 O(n)으로 나타낼 수 있게 됩니다.

그렇다면 만약 알고리즘이 반복문을 조금이라도 덜 하게 하면 좋은 시간 복잡도를 가지게 될까요?

항상 그렇지만은 않습니다.


public int solution(int[] array) {
    if(array[0] < 0) return array[0];	
    for(int i = 1; i < array.length; i++) {
        if(array[i] < 0) return array[i]
    }
    return 0;
}

이 코드는 위 코드를 조금 수정해서 반복을 데이터의 크기 n번 반복하는 것이 아닌, n-1번 반복하게 했습니다.

실제로 수행하는 코드의 양은 같기 때문에, 시간 복잡도에는 영향이 없겠죠.

그래서 우리는 위 코드의 시간 복잡도를 표기할 때 O(n-1) 이 아닌, 가장 계산에 영향을 미치는 항만 표기하여,

O(n)으로 표현합니다.

만약 n^2 + 10n + 5 번 반복해야 하는 알고리즘이 있다고 가정해봅시다.

이 경우에도 가장 영향을 미치는 항만 표현을 해서 O(n^2) 으로 나타낼 수 있겠죠.

가장 빠른 알고리즘을 찾아서

출처: www.freecodecamp.org

Big-O 표기법으로 계산한 시간 복잡도에 따른 실행 시간을 그래프로 나타내면 이러합니다.

가장 빠른 실행속도를 가진 알고리즘을 항상 사용하면 좋겠지만, 그렇지 못한 경우도 있겠죠.

사용하는 환경과 요구사항에 맞게 시간 복잡도를 생각하며 알고리즘을 짤 수 있도록 해야겠습니다.