시간 복잡도란 프로그램의 입력 값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 다시 말해 입력 크기 n에 따른 알고리즘의 연산 횟수를 수학적으로 표현한 것이다.
점근적 표기법
n 이 커질 때 알고리즘 실행 시간이 어떻게 늘어나는지를 그 함수의 증가율이라 한다. 이때 상수항과 상수배(계수), 하위 차수 항을 무시하고 증가율만 비교하면 핵심에 집중할 수 있는데, 이를 점근적 표기법(Asymptotic notation) 이라 부른다. 다시 말해 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미이다.
점근적 표기법은 다음과 같이 3가지로 나뉜다.
- 최상의 경우 : 오메가 표기법 (Big-Ω Notation) [바닥선 : “적어도 이만큼은 걸린다.”]
- 평균의 경우 : 세타 표기법 (Big-θ Notation) [정확선 : “대략 이만큼이다.”]
- 최악의 경우 : 빅오 표기법 (Big-O Notation) [천장선 : “이보다 더 느리진 않다.”]
프로그래밍에서는 대부분 빅오 표기법을 시간복잡도 표기법으로 사용한다.
빅오 표기법 (Big-O Notation)
Big-O는 입력 크기 n 이 커질 때 알고리즘이 소모하는 자원(시간·메모리 등)의 상한(upper bound) 을 나타내는 점근적 표기다. 이러한 Big-O는 분석을 단순화하기 위해 상수항과 하위 차수 항을 무시하고 증가율만 본다.
아래 표는 자주 쓰는 Big-O 등급을 정리한 것이다.
O(1) : 상수 시간
입력 크기와 상관없이 연산이 한 번에 끝나는 경우
int getFirst(int[] a) {
return a[0];
}
O(log N) : 로그 시간
연산을 한 번 할 때마다 절반(혹은 일정 비율) 로 남은 연산의 양을 줄이는 경우
int binarySearch(int[] a, int x) {
int l=0, r=a.length-1;
while (l<=r) {
int m = l + (r-l)/2;
if (a[m]==x) return m;
if (a[m]<x) l=m+1; else r=m-1;
}
return -1;
}
O(N) : 선형 시간
입력값 크기 만큼 연산을 해야 하는 경우
int max(int[] a) {
int m = Integer.MIN_VALUE;
for (int v : a) m = Math.max(m, v);
return m;
}
O(N log N) : 선형로그 시간
log N 단계를 N번 반복하는 경우 → N × log N
// 정렬된 배열 (검색 대상)
int[] a = {1, 3, 5, 7, 9, 11, 13, 15};
// 탐색할 값들 (queries)
int[] queries = {3, 6, 11, 14};
for (int q : queries) {
int idx = Arrays.binarySearch(a, q); // Q번 × log N = O(Q log N)
System.out.println("query=" + q + ", result=" + idx);
}
O(N²) : 제곱 시간
모든 쌍(이중 루프) 또는 한 쪽 길이에 비례해 다른 쪽을 반복하는 경우
int countPairsLess(int[] a, int t) { // 모든 쌍 비교
int cnt=0;
for (int i=0;i<a.length;i++)
for (int j=i+1;j<a.length;j++)
if (a[i]+a[j] < t) cnt++;
return cnt; // O(N^2)
}
O(2^N), O(N!) : 지수/팩토리얼 시간
부분집합/순열을 전부 만들어 보는 경우 → N이 조금만 커져도 폭발
void subsets(int[] a, int idx, List<Integer> cur) {
if (idx==a.length) { /* 사용 */ return; }
subsets(a, idx+1, cur); // 포함 X
cur.add(a[idx]);
subsets(a, idx+1, cur); // 포함 O
cur.remove(cur.size()-1); // 총 2^N 경로
}
자료 구조별 시간 복잡도
아래 표는 일반적인 평균/전형적 가정을 기준으로 한 요약이다.
| Data Structures | Average | Worst | ||||
| Search | Insert | Delete | Search | Insert | Delete | |
| Array | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Sorted Array | O(log n) | O(n) | O(n) | O(log n) | O(n) | O(n) |
| Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Doubly Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
| Binary Search Tree (일반 BST) | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
'Programming' 카테고리의 다른 글
| 메시지 지향 미들웨어, 메시지 브로커, 메시지 큐 (0) | 2024.08.26 |
|---|---|
| Web Socket (6) | 2024.07.13 |
| WS(Web Server)와 WAS(Web Application Server) (0) | 2024.07.13 |
| Forward Proxy, Reverse Proxy (0) | 2024.07.12 |
| CSRF(Cross-Site Request Forgery) (0) | 2024.07.11 |
