알고리즘의 시간 복잡도 - 빅오(O) 표기법

수 많은 알고리즘이 존재하지만, 어떤 알고리즘이 성능이 좋은지 평가하는 확실한 방법은 무엇일까?

방법은 수학적으로 증명하는 방법이다.

 

빅오(O) 표기법

빅오 표기법은 알고리즘의 성능 평가 방법 중 가장 많이 사용하는 방법 중 하나다.

가장 많이 사용하는 이유는 최악의 성능을 측정할 수 있기 때문이다. (최악의 성능을 알 수 있다면, 적어도 이 정도의 성능은 보장한다는 뜻이므로)

 

빅오 표기법 이외에도 오메가 표기법(Omega Notation), 세타 표기법(Theta Notation) 이 있지만, 본 글에서는 빅오 표기법에 대해서만 논한다.

알고리즘 분석하기

분석하기 전, 가정 3가지

• 헤더 파일은 알고리즘의 성능에 영향을 주지 않는다.
• 함수 진입, 함수 반환은 알고리즘 성능에 영향을 주지 않는다.
• 프로그램은 첫번째 줄 부터 마지막 줄까지 차례로 실행된다.

 

위 가정 3가지를 참고하여 아래 코드의 실행횟수를 계산해보면

#include <stdio.h> // 영향을 주지 않는다.

void main(int) // 영향을 주지 않는다.
{
    int sum = 0; // 실행 횟수: 1회
    int i; // 실행횟수: 1회
    
    for(i=1; i<=100; i++) { // 실행 횟수: 101회
    	sum = sum + i; // 실행 횟수: 100회
    }
    
    printf("1 부터 100 까지의 함: %d\n", sum); // 실행 횟수: 1회
    
    // 총 실행 횟수: 1 + 1 + 101 + 100 + 1 = 204 회
}

위 알고리즘은 총 204회의 실행 횟수를 가진다. 빅오 표기법으로 표현하면 O(204) = O(1) 이다.

상수는 알고리즘 성능에 영향을 주지 않는다. 그래서, O(상수) 는 O(1)로 표현한다.

 

하지만, 1 부터 100까지 더하는 알고리즘이 아닌 1 부터 n까지 더하는 알고리즘의 경우는

(빅오 표기법으로 계산 했을때) 알고리즘의 시간 복잡도는 O(n)이 된다.

...    

for(i=1; i<=N; i++) { // N 크기에 따라 실행 횟수가 달라진다.
    sum = sum + i;
}

...

 

위와 같은 방식으로 알고리즘의 성능을 평가한다.

 

상수항은 무시

big-O는 단순히 증가하는 비율을 나타내는 개념으로, 특수한 입력에 대해서는 O(N)이 O(1)보다 빠르게 동작할 수도 있다.

 

시간복잡도를 계산할때는 상수항을 무시한다.

• 예를들어, O(2N) ==> O(N) 으로 표기

 

지배적이지 않은 항은 무시

수식에서 가장 영향력이 있는 항을 제외한 나머지 항은 무시한다.

• 예를들어, O(N^2 + N) 이 있을때 N^2이 가장 영향력이 큰 항이므로 O(N^2)로 표현할 수 있음
  • O(N^2 + N) ==> O(N^2)
  • O(N + logN) ==> O(N)
  • O(1000*2^N + 1000N^100) ==> O(2^N)

 

빅오 표기법의 종류

O(1)

데이터 양과 상관없이 일정한 실행 시간을 가짐.

상수 함수

O(logN)

데이터 양의 증가에 따라 실행 시간이 로그 함수(logN) 그래프를 가짐.

데이터가 많이 늘어나도 실행시간이 약간씩 증가하는 특징이 있음.

로그함수 (Credit. Wiki)

O(N)

데이터 양의 증가에 따라 실행 시간이 일차 함수(N) 그래프를 가짐.

데이터의 증가량과 정비례하여 실행시간이 증가하는 특징이 있음.

 

O(NlogN)

데이터 양의 증가에 따라 실행 시간이 일차 함수 + 로그함수 (NlogN)그래프를 가짐.

데이터의 증가량보다 더 많이 실행시간이 증가하는 특징이 있음.

 

O(N^2)

데이터의 양의 증가에 따라 실행 시간이 이차 함수 (N^2) 그래프를 가짐.

데이터의 증가량에 따라 실행시간이 제곱근으로 증가하기 때문에 (일반적으로) 좋은 알고리즘은 아니다.

for(i=0; i<N; i++) {
    for(j=0; j<N; j++) {
        // Algorithm
    }
}

보통 2번 중첩된 반복문(for, while)을 사용하는 알고리즘에 해당한다.

 

O(N^3)

데이터의 양의 증가에 따라 실행 시간이 삼차 함수 (N^3) 그래프를 가짐.

실행시간이 세제곱 만큼 증가하는 알고리즘이므로 비효율적이다.

 

O(2^N)

데이터의 양의 증가에 따라 실행 시간이 지수 함수 (2^N) 그래프를 가짐.

알고리즘의 성능이 지수함수로 나온다면, 굉장히 비효율적인 알고리즘이다. (추천하지 않음)

지수함수 (Credit. Wiki)

결론

알고리즘의 성능은 O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > ... > O(2^N) 순으로 나타낼 수 있다.

Credit. Thomas J Cortina, Carnegie Mellon University

참고

• 2020/06/03 - [Algorithm] - 시간 복잡도 (빅오, 빅오메가, 빅세타)

시간 복잡도 (빅오, 빅오메가, 빅세타)

Reference

알고리즘 문제 풀이 전략 - 한빛미디어