알고리즘 시간 복잡도(Complexity) 쉽게 이해하기

복잡도란?

알고리즘의 성능을 나타내는 척도입니다.

복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있습니다.

시간 복잡도

알고리즘 문제를 해결할 때 단순히 '복잡도'라고 하면 보통 시간 복잡도를 의미합니다.

시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하며, 알고리즘을 위해 필요한 연산의 횟수 또한 의미합니다.

시간 복잡도를 표현할 떄는 빅오(Big-O) 표기법을 사용합니다. 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법입니다.

다음 아래 빅오 표기법 표는 위쪽에 있을수록 더 빠릅니다.

빅오 표기법	명칭	설명
O(1)	상수 시간(Constant time)	문제를 해결하는데 오직 한 단계 처리
O(logN)	로그 시간(Log time)	문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
O(N)	선형 시간	문제를 해결하기 위한 입력 N 만큼 단계가 필요
O(NlogN)	로그 선형 시간	문제를 해결하기 위한 단계의 수가 N번에 그 하나의 N번당 단계들이 연산마다 특정 요인에 의해 줄어듬
O(N^2)	이차 시간	문제를 해결하기 위한 단계의 수는 입력값 N의 제곱
O(2^N)	지수 시간	문제를 해결하기 위한 단계의 수는 주어진 상수값 2의 N제곱

 

1. O(1)

int a = 4;
int b = 8;

System.out.println(a + b);

위 소스코드의 연산 횟수는 1입니다. 단순히 더하기 연산 한 번이 수행되기 때문에 이는 상수 연산이므로 시간 복잡도는 O(1)로 표현할 수 있습니다.

 

2. O(logN)

이진 탐색을 예로 들 수 있습니다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기 때문에 확인하는 데이터 개수가 절반씩 줄어든다는 점에서 O(logN)로 표현할 수 있습니다.

 

3. O(N)

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

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

System.out.println(sum);

위 소스코드와 같이 array가 커짐에 따라 비례하여 연산을 수행하는 루프문 부분이므로 시간 복잡도는 O(N)으로 표현할 수 있습니다. 

 

4. O(NlogN)

합병 정렬, 퀵 정렬을 예로 들 수 있습니다. 합병정렬의 분할 단계에서 분할되는 깊이가 logN에 비례합니다. 각 깊이별로 분할이 수행되어 합병해야 되는 배열의 수는 많아지지만, 총 원소의 수는 똑같습니다. (N개)

따라서, 각 깊이별로 수행되는 merge의 시간복잡도는 O(N)이 되며, 이것을 모든 깊이에 대하(logN개만큼) 수행하기 때문에 시간 복잡도는 O(NlogN)으로 표현할 수 있습니다.

 

5. O(N^2)

int[] array = {3, 5, 2, 1, 4};

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

위 소스코드와 같이 array 크기만큼 중첩루프를 사용하여 연산 수행하므로 시간 복잡도는 O(N^2)으로 표현할 수 있습니다.

 

6. O(2^N)

대표적으로 피보나치 수열을 예로 들 수 있습니다. 재귀가 역기능을 할 경우 해당 대며, 데이터량이 많아질수록 처리시간이 기하급수적으로 증가합니다.

References

「이것이 코딩테스트다」 - 한빛미디어 (나동빈 저)