알고리즘 시간복잡도 정의 및 기본 개념 파악하기

대학교 교과 과정에서 들어봤을 법한 시간 복잡도는 대체 무엇일까? 필자도 최근에 알고리즘 문제를 많이 접하면서 다양한 알고리즘 구현 방법에 대해서 알아가고있다.

 

알고리즘 문제를 해결할 때의 핵심이 바로 시간 복잡도다. 시간 복잡도란 입력값의 변화에 따라 연산을 실행할 때 걸리는 시간을 말하는 것으로 시간 복잡도가 낮을 수록 효율적인 알고리즘이라고 할 수 있다.

 

시간 복잡도 표기법

Big-O (빅-오) : 최악

Big-Ω (빅-오메가) : 최고

Big-θ (빅-세타) : 평균

 

시간 복잡도를 표기하는 방법에는 위와 같이 총 3가지가 있다.

빅-오 표기법은 최악의 경우를 고려한다. 즉, 프로그램이 실행되는 과정에서 소요되는 최악의 시간을 생각한다. 어떠한 프로그램이든 최악의 사태를 미리 방지하고 고려해야하기 때문에 시간 복잡도는 주로 빅-오 표기법으로 작성한다.

 

시간 복잡도

1. O(1)

int A = 5;
int B = 10;

System.out.println(A + B); // 15

연산 횟수를 1회 가지는 코드이다. A 또는 B의 값을 N이라고 가정했을 시에 어떠한 숫자가 들어가도 연산에 걸리는 시간은 같다. 즉, O(1) 로 표현된다.

 

2. O(logN)

while (max >= min) {
    mid = (min + max) / 2;
            
    if (cnt < N) {
        max = mid - 1;
    } else {
        min = mid + 1;
    }
}

코드를 보면 알 수 있듯이 이분 탐색이며, 시간 복잡도는 O($log_{2}N$) 이다.  

 

전체 데이터 수를 N개라고 가정했을 때 탐색을 거칠 때 마다 1/2씩 줄어든다.

1. 첫 번째 탐색 후 $\frac{N}{2}$개
2. 두 번째 탐색 후 $\frac{N}{2}$ x $\frac{1}{2}$개
3. N 번째 탐색 후 $\frac{N}{2}$ x $\frac{1}{2}$ x $\frac{1}{2}$ ··· $\frac{1}{2}$개 → $(\frac{1}{2}) ^{K}$ x N

이분탐색은  $(\frac{1}{2}) ^{K}$ x N = 1이 될 때까지 탐색을 한다.

위 식의 양변에 $2^{K}$ 를 곱해주면 $2^{K}$ = N 이 되고, 다시 양변에  $log_{2}$ 를 취해주면

최종적으로 시간 복잡도는 O($log_{2}N$) 이 된다.

 

3. O(N)

int[] arr = {1, 2, 3, 4, 5};
int sum = 0;

for (int i=0; i<arr.length; i++) {
    sum += arr[i];
}

System.out.println(sum); // 15

반복문을 보면 배열 크기 N에 따라서 연산 횟수가 정해진다. 그렇기 때문에 시간 복잡도는 O(N) 이다.

 

4. O(NlogN)

시간 복잡도 O(NlogN) 을 가지는 대표적인 알고리즘은 분할정복 알고리즘 중에서 합병 정렬이다.

합병 정렬은 분할되는 깊이가 logN에 비례하고, 각 깊이에서 수행되는 merge의 시간 복잡도는 O(N) 이다.

즉, 합병 정렬의 시간 복잡도는 O(NlogN) 을 가진다.

 

5. O($N^{2}$)

int[] arr = {1, 2, 3};

for (int i=0; i<arr.length; i++) {
    for (int j=0; j<arr.length; j++) {
        System.out.println(i+j);
    }
}

배열 크기만큼 2중 for문을 사용하면 i = N, j = N 으로 N번씩 N번 돌아가는 구조이기 때문에 시간 복잡도는 O($N^{2}$) 가 된다. 

 

6. O($2^{N}$)

위 시간 복잡도를 가지는 가장 대표적인 알고리즘은 피보나치 수열이 있다. 입력값이 커질수록 데이터를 처리하는 시간이 엄청나게 늘어난다. 피보나치 수열의 시간 복잡도를 줄이기 위해선 여러가지 방법이 있겠지만 대표적으로 dp가 있다. dp를 사용하게 되면 시간 복잡도가 O(N)으로 줄어든다.

 

시간 복잡도의 크기: O(1) < O(logN) < O(N) < O(NlogN) < O($N^{2}$) < O($2^{N}$)

 

대표적인 알고리즘 구현 방법의 시간 복잡도

• DP : O(N)
• bfs, dfs : 크게 인접 행렬을 사용했을 때와 인접 리스트를 사용했을 때로 나누어진다. 인접 행렬: O($N^{2}$) / 인접 리스트: O(N+E) (N: 노드 개수, E: 간선 개수) 
• 다익스트라 : O(ElogV)
• 최소 비용 신장 트리 (MST) 에는 프림 알고리즘과 크루스칼 알고리즘이 있다. 

프림 알고리즘	크루스칼 알고리즘
binary heap 을 사용했을 때 : O(ElogV) unsorted array 을 사용했을 때 : O($V^{2}$)	O(ElogE)

최소 비용 신장 트리 알고리즘을 해결할 때 그래프 내의 간선의 개수(E) 가 적을 경우에는 크루스칼 알고리즘을 사용하는 게 유리하고, 간선의 개수(E) 가 많을 경우 프림 알고리즘을 사용해서 해결하는 게 유리하다는 것을 알 수 있다.