개념
시간 복잡도
는 알고리즘의 효율성
을 측정
하는 데 사용되는 중요한 개념입니다. 이는 알고리즘이 실행
되는 데 걸리는 시간
과 입력 데이터의 크기
사이의 관계
를 나타냅니다. 시간 복잡도를 분석함으로써 우리는 알고리즘이 입력 크기
가 커짐에 따라
얼마나 빠르게 실행 시간
이 증가하는지 예측
할 수 있습니다.
시간 복잡도를 설명할 때 주로 사용되는 표기법은 빅오 표기법(Big-O notation)
입니다. 빅오 표기법은 최악의 경우를 나타내며, 알고리즘의 성능을 표현하는 데 사용됩니다.
주요 시간 복잡도 종류
하나. O(1) - 상수 시간 복잡도 (Constant Time)
- 입력 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘.
- 예: 배열의 특정 인덱스에 접근하기.
둘. O(log n) - 로그 시간 복잡도 (Logarithmic Time)
- 입력 크기가 커질수록 실행 시간이 로그함수 형태로 증가하는 알고리즘.
- 예: 이진 탐색(Binary Search).
셋. O(n) - 선형 시간 복잡도 (Linear Time)
- 입력 크기에 비례하여 실행 시간이 증가하는 알고리즘.
- 예: 배열의 모든 원소를 한 번씩 탐색하는 알고리즘.
넷. O(n log n) - 선형 로그 시간 복잡도 (Linearithmic Time)
- 선형 시간과 로그 시간의 복합 형태.
- 예: 효율적인 정렬 알고리즘 (합병 정렬, 퀵 정렬).
다섯. O(n^2) - 이차 시간 복잡도 (Quadratic Time)
- 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘.
- 예: 버블 정렬, 삽입 정렬.
여섯. O(2^n) - 지수 시간 복잡도 (Exponential Time)
- 입력 크기가 증가할 때 실행 시간이 지수 함수 형태로 증가하는 알고리즘.
- 예: 피보나치 수열의 비효율적인 재귀적 구현.
일곱. O(n!) - 팩토리얼 시간 복잡도 (Factorial Time)
- 입력 크기의 팩토리얼에 비례하여 실행 시간이 증가하는 알고리즘.
예: 순열 생성 알고리즘.
시간 복잡도 분석의 중요성
- 성능 예측: 입력 데이터가 매우 큰 경우에도 알고리즘이 효율적으로 작동할 수 있는지 예측할 수 있습니다.
- 자원 절약: 효율적인 알고리즘을 사용함으로써 시스템 자원을 절약하고, 성능을 최적화할 수 있습니다.
- 비교 기준: 여러 알고리즘을 비교할 때 시간 복잡도는 중요한 기준이 됩니다.
예제
각 시간 복잡도를 설명하기 위해 Java 코드 예제를 포함하여 설명하겠습니다.
1. O(1) - 상수 시간 복잡도 (Constant Time)
입력 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘입니다.
public int getFirstElement(int[] arr) {
return arr[0]; // 항상 일정한 시간에 실행
}
2. O(log n) - 로그 시간 복잡도 (Logarithmic Time)
입력 크기가 커질수록 실행 시간이 로그함수 형태로 증가하는 알고리즘입니다.
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 찾지 못했을 때
}
3. O(n) - 선형 시간 복잡도 (Linear Time)
입력 크기에 비례하여 실행 시간이 증가하는 알고리즘입니다.
public int findMax(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
return max;
}
4. O(n log n) - 선형 로그 시간 복잡도 (Linearithmic Time)
선형 시간과 로그 시간의 복합 형태입니다.
import java.util.Arrays;
public void sortArray(int[] arr) {
Arrays.sort(arr); // 정렬 알고리즘 (예: 합병 정렬, 퀵 정렬)이 O(n log n)의 시간 복잡도를 가짐
}
5. O(n^2) - 이차 시간 복잡도 (Quadratic Time)
입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘입니다.
public void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
6. O(2^n) - 지수 시간 복잡도 (Exponential Time)
입력 크기가 증가할 때 실행 시간이 지수 함수 형태로 증가하는 알고리즘입니다.
public int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
7. O(n!) - 팩토리얼 시간 복잡도 (Factorial Time)
입력 크기의 팩토리얼에 비례하여 실행 시간이 증가하는 알고리즘입니다.
public void generatePermutations(int[] arr, int n) {
if (n == 1) {
System.out.println(Arrays.toString(arr));
return;
}
for (int i = 0; i < n; i++) {
generatePermutations(arr, n - 1);
if (n % 2 == 0) {
int temp = arr[i];
arr[i] = arr[n - 1];
arr[n - 1] = temp;
} else {
int temp = arr[0];
arr[0] = arr[n - 1];
arr[n - 1] = temp;
}
}
}
각 시간 복잡도에 대한 예제는 다양한 입력 크기에 대한 알고리즘의 성능을 이해하는 데 도움이 됩니다. 이 예제들을 통해 알고리즘의 효율성을 평가하고 적절한 알고리즘을 선택하는 능력을 기를 수 있습니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준]알고리즘의 수행 시간 2 - 24263번 (0) | 2024.05.31 |
---|---|
[백준]알고리즘의 수행 시간 4 - 24265번 (0) | 2024.05.31 |
[백준]알고리즘의 수행 시간 2 - 24263번 (0) | 2024.05.31 |
[백준] 숫자놀이 - 1755번 (0) | 2024.05.30 |
[백준] 파일 정리 - 20291번 (1) | 2024.05.30 |