[알고리즘] 시간복잡도와 빅오(Big O), 오메가($\Omega$) 표기법

시간 복잡도란?

시간 복잡도란 알고리즘의 성능을 나타내는 지표로 입력횟수에 대한 연산 횟수 상한을 의미합니다. 따라서 시간 복잡도가 낮을 수록 연산 횟수가 줄어들고 효율적인 알고리즘이 됩니다.

 

 

알고리즘 시간 측정 방법

알고리즘의 성능 측정을 위해서는 2가지의 측정 방법이 있는데 하나는 절대 시간을 측정하는 방법이고 하나는 시간복잡도를 측정하는 것이다.

 

 

 절대 시간 측정

말 그대로 프로세스가 실행되고 종료되는 시간을 측정하는 것이다. 그런데 이 방식의 문제는 실행환경에 따라서 결과 값이 달라진다는 것이다. 그래서 코딩 테스트와 같은 환경에서 사용은 부적합하다.

 

 

 시간 복잡도 측정

이 방식은 연산 횟수를 바탕으로 시간을 표현한다. 그래서 실행환경에 따른 차이 없이 동일하게 측정이 가능하다. 시간 복잡도를 나태는 방식은 3가지가 있다.

• 오메가 표기법 : 최상의 경우를 표시 
• 세타 표기법 : 평균의 경우 를 표시 
• 빅오 표기법 : 최악의 경우 를 표시 

 

 

 1차원 배열 검색

알고리즘이 for문을 통해 하나씩 배열에서 내가 찾는 값을 비교하면서 찾는다고 가정해보자

 

- 가장 빨리 찾는 경우 x = 1인경우 1번의 탐색으로 찾는다. $ \Omega(1)$

- 가장 느린 경우 x = n 인경우 n번의 탐색으로 찾는다. $ O(n)$

 

 

빅오(Big O) 표기법

알고리즘의 시간 복잡도 f(n)이 O(g(n)) 이라는 것은 다음을 의미한다.

f(n) $\in$ O(g(n)) $\Leftrightarrow$ 모든 $n \geq n_0$에 대하여, $0 \leq f(n) \leq c \cdot g(n)$

 

 

 

오메가($\Omega$) 표기법

알고리즘의 시간 복잡도 f(n)이 $\Omega$(g(n)) 이라는 것은 다음을 의미한다.

$f(n) \in \Omega(g(n)) \Leftrightarrow 모든 n \geq n_0에 대하여, 0 \leq c \cdot g(n) \leq f(n)$

 

 

 

예제로 알아보는 빅오와 오메가

예시를 위해 버블 정렬이라 불리는 정렬 알고리즘을 사용해볼 것이다.

버블정렬 : 인접한 두수를 계속 비교하며 정렬을 해나가는 알고리즘

class BubbleSort{

    public int[] bubbleSort(int[] arr) {

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            
            boolean end = true;
            for (int j = 0; j < n- i - 1; j++){

                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    end = false;
                }
            }

            if (end) {
                break;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        int[] arrSorted = new BubbleSort().bubbleSort(arr);

        for (int num : arrSorted) {
            System.out.print(num+", ");
        }
    }
}

 

 

 

 최악의 경우(Big O)

투입되는 배열이 역배열일 경우 연산이 $\frac{n(n-1)}{2}$번 이루어지게 된다. 따라서 시간 복잡도는 $O(n^2)$이 된다.

 

최상의 경우($\Omega$)

투입부터 정배열로 투입되어 첫번째 루프에서 배열이 완료되어 탈출하는 경우로 연산이 n번 이루어진다. 따라서 시간 복잡도는 $\Omega(n)$이 된다.