알고리즘 시간복잡도 상세 설명
출처 : https://www.bigocheatsheet.com/
시간 복잡도는 3가지 경우로 나타냅니다.
최선의 경우 (Best Case)
빅 오메가 표기법 사용
최선의 시나리오로 최소 이만한 시간이 걸림
최악의 경우 (Worst Case)
빅 오 표기법 사용
최악의 시나리오로 아무리 오래 걸려도 이 시간보다 덜 걸림
평균적인 경우 (Average Case)
빅 세타 표기법 사용
평균 시간을 나타냄
평균적인 경우를 가장 많이 사용할 것 같지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워 지기 때문에 최악의 경우로 알고리즘의 성능을 파악함.
시간 복잡도 계산과 빅오 표기법
빅오 표기법 기본
시간 복잡도는 알고리즘 성능 나타내는 척도로, 연산 횟수가 다항식일 때 최고차항만 쓰고 계수는 빼. 예를 들어, 연산 횟수가
4n+5면, 시간 복잡도는 O(n)으로 표기한다.
시간 복잡도 유형별 예시
상수 시간 (O(1)): 입력 크기 상관없이 일정한 시간 걸림
void func(int n) {
printf("%d\n", n);
}로그 시간 (O(log N)): 연산 횟수가 로그에 비례해서 증가한다.
for(i = 1; i <= n; i *= 2) {
// 로그 시간 복잡도 연산
}로그 시간 복잡도는
𝑖
i 값이 2배씩 증가할 때마다 2^𝑘 = 𝑛일 때
𝑘 = log2(𝑛) 나타낸다.
선형 시간 (O(n)): 연산 횟수가 입력 크기
n에 비례해서 증가한다.
for(i = 0; i < n; i++) {
// 선형 시간 복잡도 연산
}
이차 시간 (O(n^2)): 중첩 반복문으로 연산 횟수가
n의 제곱에 비례해서 증가한다.
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
// 이차 시간 복잡도 연산
}
}
지수 시간 (O(2^n)): 재귀적 알고리즘에서 볼 수 있으며, 연산 횟수가 입력 크기의 지수 함수로 증가한다.
int func(int n) {
if (n <= 1) return n;
return func(n-1) + func(n-2); // 피보나치 수열
}
성능 그래프 이해
빅오 치트 시트에서 다양한 알고리즘 성능 비교 가능해. 오른쪽으로 갈수록 시간 복잡도 높아져서 성능이 떨어진다.
n 값이 클수록 복잡도 높은 알고리즘은 실행 시간이 급격히 길어진다.
시간 복잡도 잘 관리하면 프로그램 성능 크게 올릴 수 있어. 특히 큰 데이터 처리하거나 반응성 중요한 앱에서 중요하게 나타낼 수 있다.
| 시간 복잡도 유형 | 빅오 표기법 | 설명 | 예시 |
|---|---|---|---|
| 상수 시간 | O(1) | 입력 크기와 상관없이 일정한 시간 소요 | void func(int n) { printf("%d\\n", n); } |
| 로그 시간 | O(log N) | 연산 횟수가 로그에 비례해서 증가 | for (i = 1; i <= n; i *= 2) { ... } |
| 선형 시간 | O(n) | 연산 횟수가 입력 크기 n에 비례해서 증가 | for (i = 0; i < n; i++) { ... } |
| 이차 시간 | O(n^2) | 중첩 반복문을 통해 연산 횟수가 n의 제곱에 비례해서 증가 | for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { ... } } |
| 지수 시간 | O(2^n) | 연산 횟수가 입력 크기의 지수 함수로 증가, 주로 재귀 알고리즘에 해당 | int func(int n) { if (n <= 1) return n; return func(n-1) + func(n-2); } |
정렬 알고리즘
버블 정렬
시간복잡도: 최선 O(n), 평균 O(n^2), 최악 O(n^2)
설명: 각 요소를 반복적으로 비교하고 필요에 따라 교환하여 정렬.
선택 정렬
시간복잡도: 최선 O(n^2), 평균 O(n^2), 최악 O(n^2)
설명: 가장 작은 요소를 선택해 맨 앞으로 이동, 반복적으로 진행.
삽입 정렬
시간복잡도: 최선 O(n), 평균 O(n^2), 최악 O(n^2)
설명: 각 요소를 이미 정렬된 배열의 적절한 위치에 삽입.
퀵 정렬
시간복잡도: 최선 O(n log n), 평균 O(n log n), 최악 O(n^2)
설명: 피벗을 기준으로 파티셔닝 후, 분할 정복 방식으로 정렬.
병합 정렬
시간복잡도: 최선 O(n log n), 평균 O(n log n), 최악 O(n log n)
설명: 분할 정복을 사용하여 배열을 반복적으로 나눈 후 병합하면서 정렬.
| 정렬 알고리즘 | 최선의 경우 | 평균의 경우 | 최악의 경우 | 설명 |
|---|---|---|---|---|
| 버블 정렬 | O(n) | O(n^2) | O(n^2) | 인접한 요소를 반복적으로 비교하고 교환하여 정렬 |
| 선택 정렬 | O(n^2) | O(n^2) | O(n^2) | 최소 요소를 찾아 맨 앞으로 이동, 반복적으로 정렬 |
| 삽입 정렬 | O(n) | O(n^2) | O(n^2) | 각 요소를 이미 정렬된 배열의 적절한 위치에 삽입 |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n^2) | 피벗을 기준으로 작은 요소와 큰 요소를 분할하여 정렬 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) | 배열을 반복적으로 나눈 뒤 병합하며 정렬 |
| 힙 정렬 | O(n log n) | O(n log n) | O(n log n) | 최대 힙 트리 구조를 사용하여 정렬 |
| 기수 정렬 | O(nk) | O(nk) | O(nk) | 숫자의 각 자리수에 따라 숫자를 분류하고 수집 |
| 쉘 정렬 | O(n log n) | O(n(log n)^2) | O(n(log n)^2) | 일정 간격으로 떨어진 요소들끼리 삽입 정렬 수행 후 간격 줄임 |
탐색 알고리즘
선형 탐색
시간복잡도: 최선 O(1), 평균 O(n), 최악 O(n)
설명: 배열을 처음부터 끝까지 순차적으로 탐색.
이진 탐색
시간복잡도: 최선 O(1), 평균 O(log n), 최악 O(log n)
설명: 정렬된 배열에서 중앙 값을 기준으로 반을 나눠가며 탐색.
그래프 알고리즘
깊이 우선 탐색 (DFS)
시간복잡도: O(V+E)
설명: 루트 노드(또는 임의의 노드)에서 시작해 가능한 한 깊게 그래프를 탐색.
너비 우선 탐색 (BFS)
시간복잡도: O(V+E)
설명: 루트 노드(또는 임의의 노드)에서 인접한 노드를 먼저 탐색, 계층적으로 확장.
다익스트라 알고리즘
다익스트라 알고리즘
시간복잡도: 우선순위 큐 사용 시 O((V+E) log V)
설명: 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾음. 음의 가중치가 없어야 함.
프림 알고리즘
프림 알고리즘
시간복잡도: 우선순위 큐 사용 시 O((V+E) log V)
설명: 최소 신장 트리를 구성, 연결된 모든 정점을 최소 비용으로 연결.
크루스칼 알고리즘
크루스칼 알고리즘
시간복잡도: O(E log E) 또는 O(E log V)
설명: 최소 신장 트리를 구성, 간선을 가중치 순으로 정렬 후 선택.
유니온-파인드 알고리즘
유니온-파인드
시간복잡도: 거의 O(1), 아모티즈드 O(α(N))
설명: 노드 집합의 연결 상태를 관리, 두 노드의 연결 여부를 빠르게 확인.
| 알고리즘 종류 | 알고리즘 이름 | 시간 복잡도 | 설명 |
|---|---|---|---|
| 탐색 알고리즘 | 선형 탐색 | O(n) | 배열을 순차적으로 탐색 |
| 탐색 알고리즘 | 이진 탐색 | O(log n) | 정렬된 배열에서 중간 값을 통한 탐색 |
| 그래프 알고리즘 | 깊이 우선 탐색 (DFS) | O(V+E) | 그래프의 모든 노드를 깊이 우선으로 탐색 |
| 그래프 알고리즘 | 너비 우선 탐색 (BFS) | O(V+E) | 그래프의 모든 노드를 너비 우선으로 탐색 |
| 그래프 알고리즘 | 다익스트라 | O((V+E) log V) | 시작 노드로부터 다른 모든 노드까지의 최단 경로 |
| 그래프 알고리즘 | 프림 | O((V+E) log V) | 가중치 그래프에서 최소 신장 트리 생성 |
| 그래프 알고리즘 | 크루스칼 | O(E log E) | 가중치 그래프에서 최소 신장 트리 생성 |
| 자료 구조 | 유니온-파인드 | O(α(N)) | 서로소 집합 자료구조로 그룹 관리와 합치기 |
