[algorithm] 시간 복잡도 계산 방법 + 표기법

효율적인 알고리즘을 짜기 위해선 런타임과 메모리 사용을 최소화시키는 것이 중요하다. 그 중 런타임, 즉 시간 복잡도를 계산하는 법을 먼저 알아보겠다.

 

표기법

시간복잡도 표기 방식에는 아래와 같이 세가지가 있다.

• 최상의 경우: 오메가 표기법 (Big-Ω Notation)
• 최악의 경우: 빅오표기법 (Big-O Notation)
• 평균의 경우: 세타 표기법 (Big-θ Notation)

 

일반적으로 가장 많이 사용되는 것은 빅오 표기법이다. 빅오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. (예, 2n²-2n+2 > O(n^2)로 표기) 빅오 표기법이 개발자들에게 중요한 이유는, 최악의 경우를 대비해서 알고리즘을 짜야하기 때문이다. 빅오 표기법에 가장 큰 영향을 미치는 것은 input의 개수이다. Input N 하나 기준으로 몇번의 연산이 반복되는지 계산한 것이 빅오표기법이다.  

 

Big-O Notation Cases

1. O(1) – 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.
2. O(log n) – 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
3. O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.
4. O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.
5. O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다.

 

BIG O NOTATION 알고리즘 예시

O(log n)	Binary search
O(n)	Simple search
O(n * log n)	Quicksort
O(n2)	Selection sort
O(n!)	Traveling salesperson

 

BIG O Complexity 계산법

1. 상수를 제거한다.

void printAllItemsTwice(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d\n", arr[i]);
    }
	
    for (int i = 0; i < size; i++)
    {
        printf("%d\n", arr[i]);
    }
}

위와 같은 경우에는 array에 대해서 두번의 code execution이 진행되기 때문에 O(2n)이다. 상수를 제거해줘서 O(n)이 된다.

void printFirstItemThenFirstHalfThenSayHi100Times(int arr[], int size)
{
    printf("First element of array = %d\n",arr[0]);
	
    for (int i = 0; i < size/2; i++)
    {
        printf("%d\n", arr[i]);
    }

    for (int i = 0; i < 100; i++)
    {
        printf("Hi\n");
    }
}

위와 같은 경우에는 time complexity는 O(1 + n/2 + 100)로 계산된다. 이 역시 상수를 제거해줘서 O(n)이 된다.

 

2. 가장 큰 차수의 항만 남긴다.

void printAllNumbersThenAllPairSums(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d\n", arr[i]);
    }

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            printf("%d\n", arr[i] + arr[j]);
        }
    }
}

위와 같은 경우에는 time complexity는 O(n + n^2)로 계산된다. N이 커질 수록 더 영향력이 큰 항, 즉 가장 큰 차수의 항만 남겨두고 삭제해준다. 따라서 위의 코드는 O(n^2)이다.

비슷한 논리로 다음과 같이 표현될 수 있다:

• O(n3 + 50n2 + 10000) -> O(n3)
• O((n + 30) * (n + 5)) -> O(n2)