시간 복잡도란?
시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 수학적으로 분석한 것이다. 특히, 입력 데이터의 크기(데이터 개수)가 커질 때 알고리즘의 수행 시간이 어떻게 변하는지를 나타낸다. 시간 복잡도를 통해 우리가 작성한 코드가 얼마나 효율적인지, 데이터가 커지면 성능이 어떻게 변할지를 미리 파악할 수 있다.
빅오 표기법 (Big-O Notation)
시간 복잡도는 보통 빅오(Big-O) 표기법을 사용해 나타낸다. 빅오 표기법은 최악의 경우 걸리는 시간을 나타내는 방법으로, 입력 데이터의 크기(보통 n으로 표기)에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 표현한다. 빅오 표기법의 주요 형태는 다음과 같다.
- O(1): 상수 시간
- O(log n): 로그 시간
- O(n): 선형 시간
- O(n log n): 선형 로그 시간
- O(n^2): 제곱 시간
빅오 표기법의 주요 시간 복잡도와 예시
1. O(1): 상수 시간
O(1)은 입력 데이터의 크기와 관계없이 항상 일정한 시간이 걸리는 경우를 나타낸다. 예를 들어, 배열의 첫 번째 요소에 접근하는 작업은 데이터가 몇 개든 한 번만 접근하면 되기 때문에 상수 시간 복잡도를 가진다.
// 배열의 첫 번째 요소에 접근하는 예시
int[] array = {1, 2, 3, 4, 5};
int firstElement = array[0]; // O(1)2. O(log n): 로그 시간
O(log n)은 입력 데이터의 크기가 커질수록 시간이 천천히 증가하는 경우이다. 이진 탐색(Binary Search) 알고리즘이 대표적이다. 예를 들어, 정렬된 배열에서 원하는 값을 찾을 때, 중간 값을 기준으로 탐색 범위를 절반씩 줄이므로 로그 시간이 걸린다.
// 이진 탐색의 예시
int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) return mid; // O(log n)
if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}3. O(n): 선형 시간
O(n)은 데이터가 증가함에 따라 시간이 비례해서 증가하는 경우이다. 예를 들어, 배열에서 특정 값을 찾기 위해 모든 요소를 하나씩 확인하는 작업은 배열의 길이에 비례해서 시간이 걸린다.
// 선형 탐색의 예시
int linearSearch(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) return i; // O(n)
}
return -1;
}4. O(n log n): 선형 로그 시간
O(n log n)은 많은 정렬 알고리즘에서 나타난다. 예를 들어, 병합 정렬(Merge Sort)이나 퀵 정렬(Quick Sort)은 데이터가 많아질수록 𝑛 log 𝑛 시간에 비례하여 동작한다.
5. O(n^2): 제곱 시간
O(n^2)은 데이터가 증가할 때 시간이 제곱으로 증가하는 경우이다. 예를 들어, 버블 정렬과 같은 비교 기반의 단순 정렬 알고리즘은 모든 요소를 서로 비교하기 때문에 시간이 제곱으로 늘어난다.
// 버블 정렬의 예시
void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) { // O(n^2)
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}시간 복잡도를 이해해야 하는 이유
시간 복잡도는 코드의 성능을 예측하고, 데이터가 많아질 때 효율적으로 작동하는지를 미리 판단하는 데 중요하다. 데이터 양이 늘어날수록 성능이 급격히 떨어지는 알고리즘을 피하고, 효율적인 알고리즘을 선택하는 데 도움을 준다.
시간 복잡도 분석 시 주의할 점
- 최악의 경우를 고려: 시간 복잡도는 주로 최악의 경우를 가정하고 분석한다.
- 빅오 표기법의 한계: 실제 상황에서는 데이터의 분포나 특성에 따라 성능이 달라질 수 있으므로, 복합적인 상황을 함께 고려해야 한다.
결론
시간 복잡도는 데이터의 양이 증가함에 따라 알고리즘이 얼마나 효율적으로 동작하는지 보여주는 중요한 지표이다. 이를 통해 효율적인 알고리즘을 선택할 수 있으며, 성능을 최적화할 때 중요한 기준이 된다. 데이터가 커질수록 시간 복잡도에 따른 성능 차이는 더 커지므로, 알고리즘 설계 시 시간 복잡도를 반드시 고려해야 한다.
