시간 복잡도와 공간 복잡도
✏️ 시간 복잡도
시간 복잡도는 어떤 알고리즘이 문제를 해결하는 데 소요되는 시간이 입력의 크기에 따라 어떻게 변하는지를 나타냅니다. 이는 일반적으로 최악의 경우(worst-case)를 기준으로 측정되며, 때로는 평균적인 경우(average-case)나 최선의 경우(best-case)도 고려됩니다.
빅오(Big-O) 표기법이은 알고리즘의 성능을 최악의 상황에서 분석하기 위해 사용되는 표현 방법입니다. 예를 들어, O(n)은 알고리즘이 입력 데이터의 크기(n)와 비례하여 시간이 증가한다는 것을 의미합니다.
추가적인 표기법으로 빅오메가(Ω) 표기법과 빅세타(Θ) 표기법이 있으며 각 표기법의 역할은 다음과 같습니다.
- 빅오메가(Ω) 표기법 - 알고리즘의 최선 성능을 나타냅니다. 예를 들어, Ω(n)은 알고리즘이 최선의 경우 n에 비례하는 시간이 소요된다는 것을 의미합니다.
- 빅세타(Θ) 표기법 - 알고리즘의 평균적인 성능을 나타냅니다. 예를 들어, Θ(n)은 평균적이 경우에 알고리즘이 n에 비례하는 시간이 걸린다는 것을 의미합니다.
❗️ 시간 복잡도의 중요성
시간 복잡도는 컴퓨터 프로그램 또는 알고리즘의 효율성을 평가하는 중요한 도구입니다. 이는 특히 자원이 제한적이거나 대규모 데이터를 처리할 때 더욱 중요해집니다. 시간 복잡도의 주요 목적은 다음과 같습니다.
- 성능 예측 : 시간 복잡도를 통해 주어진 입력 크기에 대해 알고리즘이 얼마나 빠르게 실행될지 예측할 수 있습니다. 이는 시스템 설계 및 리소스 할당에 중요한 정보를 제공합니다.
- 알고리즘 비교 : 다양한 알고리즘 중 어떤 것이 특정 상황에 가장 적합한지 결정할 때 시간 복잡도를 기준으로 사용합니다.
- 성능 최적화 : 시간 복잡도를 이해함으로써 알고리즘을 더 효율적으로 만들기 위한 개선점을 찾을 수 있습니다.
- 자원 관리 : 시스템의 처리 능력과 메모리 제한을 고려하여 가장 적합한 알고리즘을 선택할 수 있습니다.
📌 빅오(Big-O) 표기법의 종류
- O(1) - 상수 시간(Constant Time)
function getFirstElement(array) {
return array[0];
}
배열의 첫 번째 요소를 반환합니다. 배열의 크기와 관계없이 항상 동일한 시간이 걸립니다.
- O(log n) - 로그 시간(Logarithmic Time)
function binarySearch(array, key) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const guess = array[mid];
if (guess === key) {
return mid;
}
if (guess > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return null;
}이진 탐색 알고리즘으로, 정렬된 배열에서 원하는 값을 효율적으로 찾습니다.
- O(n) - 선형 시간(Linear Time)
function findMax(array) {
let max = array[0];
for (let i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
return max;
}배열을 순회하며 최댓값을 찾습니다. 배열의 크기가 커질수록 시간도 선형적으로 증가합니다.
- O(n log n) - 선형 로그 시간(Linear Logarithmic Time)
function merge(left, right) {
let result = [], leftIndex = 0, 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.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
function mergeSort(array) {
if (array.length <= 1) {
return array;
}
const middle = Math.floor(array.length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
let array = [12, 11, 13, 5, 6, 7];병합 정렬과 같은 정렬 알고리즘은 대표적인 O(n log n) 시간 복잡도를 가집니다.
- O(n^2) - 이차 시간(Quadratic Time)
function bubbleSort(array) {
let len = array.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (array[j] > array[j + 1]) {
let temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}버블 정렬은 두 개의 중첩된 루프를 사용하여 배열을 정렬합니다.
- O(2^n) - 지수 시간(Exponential Time)
function fibonacci(num) {
if (num <= 1) return num;
return fibonacci(num - 1) + fibonacci(num - 2);
}피보나치수열의 재귀적 계산은 2^n의 시간 복잡도를 가지며 매우 비효율적입니다.
- O(n!) - 팩토리얼 시간(Factorial Time)
function permute(arr, l = 0, r = arr.length - 1) {
if (l === r) {
console.log(arr);
} else {
for (let i = l; i <= r; i++) {
[arr[l], arr[i]] = [arr[i], arr[l]]; // 스왑
permute(arr, l + 1, r); // 재귀 호출
[arr[l], arr[i]] = [arr[i], arr[l]]; // 복구
}
}
}
let array = [1, 2, 3];
permute(array);모든 순열을 생성하는 함수는 n!의 시간 복잡도를 가집니다. 배열의 크기가 증가하면 연산량이 굉장히 빠르게 증가합니다.
⏳ 자료 구조에서의 시간 복잡도
자료 구조에서의 평균 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열(Array) | O(1) | O(n) | O(n) | O(n) |
| 스택(Stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(Queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(Hash Table) | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리(BST) | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
| 레드 블랙 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
자료 구조에서의 최악의 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열(Array) | O(1) | O(n) | O(n) | O(n) |
| 스택(Stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(Queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(Hash Table) | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리(BST) | O(n) | O(n) | O(n) | O(n) |
| AVL 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
| 레드 블랙 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
✏️ 공간 복잡도
공간 복잡도는 프로그램이 실행되고 데이터를 처리하는 데 필요한 총 메모리 공간의 양을 나타냅니다. 이는 크게 정적 공간, 스택 공간, 힙 공간 세 가지 주요 요소로 구성됩니다.
정적 공간(Static Space)
이는 프로그램 코드의 크기와 전역 변수를 포함합니다. 이 공간은 실행 파일의 크기와 직접적인 관련이 있습니다.
스택 공간(Stack Space)
함수 내부에서 선언된 지역 변수, 함수 매개변수, 리턴 주소 등이 스택에 저장됩니다. 재귀적 함수 호출은 스택 공간 사용량을 증가시킵니다.
힙 공간(Heap Space)
동적 메모리 할당이 이루어지는 부분으로, 런타임에 필요에 따라 메모리가 할당되고 해제됩니다. 예를 들어, 자바의 new 연산자, Python의 객체 생성 등이 여기에 해당합니다.
공간 복잡도 분석은 주로 알고리즘의 메모리 효율성을 평가하는 데 사용됩니다. 예를 들어, 재귀 알고리즘은 종종 높은 스택 공간을 필요로 하며, 대규모 데이터 구조는 상당한 양의 힙 공간을 요구할 수 있습니다. 따라서 알고리즘의 메모리 사용을 최적화하는 것은 중요합니다.