시간 복잡도(Time Complexity) 이해하기
코딩 테스트를 준비하면서 자주 접하는 개념 중 하나가 바로 '시간 복잡도(Time Complexity)'이다.
이는 코드가 실행될 때 소요되는 시간을 나타내는 척도이며, 특히 대규모 데이터를 처리할 때 알고리즘의 효율성을 평가하는 데 중요한 기준이 된다. 자료구조와 알고리즘 전공 수업 때 배우긴 했다만, 해당 개념을 제대로 정리해 보면서 복습해 보고자 한다.
1. 시간 복잡도란?
시간 복잡도는 입력 크기에 따른 알고리즘의 실행 시간 변화를 분석하는 방식이다.
단순히 코드 실행 시간을 측정하는 것이 아니라, 데이터 양이 커질수록 실행 시간이 어떻게 변화하는지 그 성장률을 분석하는 것이 핵심이다. 시간 복잡도는 일반적으로 대문자 O 표기법(Big-O Notation)을 사용해 표현한다.
2. 빅오(Big-O) 표기법
빅오 표기법은 알고리즘의 성능을 수학적으로 표현하는 방법으로, 입력 크기 `n`에 따른 최악의 실행 시간 성장을 나타낸다.
여러 종류의 빅오 표기법이 있으며, 각 표기법이 의미하는 성능은 다음과 같다:
O(1): 상수 시간(Constant Time)
- 입력 크기에 상관없이 항상 일정한 시간이 소요
- 예: 배열의 인덱스로 특정 요소에 접근하기
O(log n): 로그 시간(Logarithmic Time)
- 입력 크기가 커질수록 실행 시간은 천천히 증가
- 예: 이진 탐색(Binary Search)
O(n): 선형 시간(Linear Time)
- 입력 크기에 비례하여 실행 시간이 증가
- 예: 배열의 모든 요소를 순회하는 경우
O(n log n): 선형 로그 시간(Linearithmic Time)
- 입력 크기에 로그 값을 곱한 만큼 실행 시간이 증가.
- 예: 효율적인 정렬 알고리즘(병합 정렬, 힙 정렬 등)
O(n²): 이차 시간(Quadratic Time)
- 입력 크기의 제곱에 비례하여 실행 시간이 증가
- 예: 중첩된 반복문을 사용하는 알고리즘(버블 정렬, 선택 정렬 등)
O(2ⁿ): 지수 시간(Exponential Time)
- 입력 크기가 증가함에 따라 실행 시간이 매우 빠르게 증가
- 예: 피보나치 수열의 재귀적 구현
3. 실제 예제와 시간 복잡도 분석
선형 탐색(Linear Search)
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}
이 함수는 배열을 처음부터 끝까지 순회하면서 목표값을 찾는다.
최악의 경우 배열 끝까지 탐색하므로 시간 복잡도는 O(n)이다.
이진 탐색(Binary Search)
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
이진 탐색은 정렬된 배열에서만 사용할 수 있으며, 중간 값을 기준으로 탐색 범위를 절반씩 줄여나간다.
이 알고리즘의 시간 복잡도는 O(log n)이다.
버블 정렬(Bubble Sort)
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}버블 정렬은 배열을 여러 번 순회하면서 인접한 두 요소를 비교하고, 더 큰 값을 뒤로 보낸다.
배열의 길이가 n인 경우, 내부 루프에서 한 번 비교할 때마다 n-i-1번 비교하므로, 최악의 경우 모든 요소를 두 번씩 순회하게 되므로, 시간 복잡도는 O(n²)이다.
퀵 정렬(Quick Sort)
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[arr.length - 1];
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}퀵 정렬은 피벗(pivot)을 기준으로 배열을 두 부분으로 나눈 후, 재귀적으로 두 부분을 정렬하는 분할 정복 알고리즘이다.
평균적으로는 배열을 반으로 나누는 과정에서 O(log n)이 걸리고, 각 부분을 정렬하는데 O(n)이 소요되므로
시간 복잡도는 O(n log n)이다. 하지만, 피벗이 항상 최악으로 선택되면 O(n²)가 될 수 있다.
병합 정렬(Merge Sort)
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return [...result, ...left.slice(leftIndex), ...right.slice(rightIndex)];
}병합 정렬은 배열을 두 개의 작은 배열로 나눈 후, 각각을 정렬한 다음 다시 합치는 과정으로 작동한다.
배열을 반으로 나누는 데는 O(log n)의 시간이 걸리고, 병합하는 과정에서 각 단계마다 O(n)의 시간이 소요되므로
전체 시간 복잡도는 O(n log n)이다.
삽입 정렬(Insertion Sort)
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}삽입 정렬은 배열의 두 번째 요소부터 시작하여, 그 요소가 적절한 위치에 삽입될 때까지 이전 요소들과 비교하는 알고리즘이다.
최악의 경우에는 배열의 모든 요소에 대해 비교가 이루어져야 하므로 O(n²)의 시간이 걸린다.
해시 테이블(Hash Table) 삽입과 검색
let hashTable = {};
function insertToHashTable(key, value) {
hashTable[key] = value;
}
function searchInHashTable(key) {
return hashTable[key] || null;
}해시 테이블은 해시 함수를 사용해 데이터를 빠르게 삽입하고 검색하는 자료 구조이다.
일반적으로 해시 함수는 일정한 시간이 걸리기 때문에 삽입과 검색의 시간 복잡도는 O(1)이다.
하지만, 충돌이 발생할 경우에는 성능이 저하될 수 있다.
피보나치 수열 - 재귀적 구현
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}재귀적으로 구현된 피보나치 수열은 동일한 값을 여러 번 계산하는 비효율적인 방식이다.
예를 들어 fibonacci(5)를 계산할 때 fibonacci(3)은 두 번 호출된다.
이렇게 중복된 계산이 발생하여 시간 복잡도가 O(2ⁿ)로 급격하게 증가한다.
피보나치 수열 - 동적 프로그래밍(Dynamic Programming)
function fibonacciDP(n) {
let memo = [0, 1];
for (let i = 2; i <= n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n];
}동적 프로그래밍을 사용한 피보나치 수열은 이전에 계산된 값을 저장해 중복된 계산을 피한다.
이로 인해 계산 횟수가 n번으로 제한되며, 시간 복잡도는 O(n)으로 줄어든다.