시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 걸리는 시간을 입력의 크기에 따라 측정하는 척도이다. 시간 복잡도는 알고리즘이 수행하는 연산의 수가 입력 크기에 따라 어떻게 변화하는지를 분석하여, 입력 크기가 커질 때 실행 시간이 어떻게 증가하는지를 설명한다.
#시간 복잡도의 주요 개념
- 상수 시간 복잡도 (O(1)): 알고리즘의 실행 시간이 입력 크기와 관계없이 일정하다. 예를 들어, 배열의 특정 인덱스에 접근하는 연산은 상수 시간 복잡도를 가진다.
- 로그 시간 복잡도 (O(log n)): 알고리즘의 실행 시간이 입력 크기의 로그에 비례하다. 예를 들어, 이진 탐색 알고리즘은 로그 시간 복잡도를 가진다.
- 선형 시간 복잡도 (O(n)): 알고리즘의 실행 시간이 입력 크기에 비례하다. 예를 들어, 배열의 모든 요소를 순회하는 연산은 선형 시간 복잡도를 가진다.
- 선형 로그 시간 복잡도 (O(n log n)): 알고리즘의 실행 시간이 입력 크기와 입력 크기의 로그의 곱에 비례하다. 예를 들어, 병합 정렬과 퀵 정렬 같은 효율적인 정렬 알고리즘은 선형 로그 시간 복잡도를 가진다.
- 이차 시간 복잡도 (O(n^2)): 알고리즘의 실행 시간이 입력 크기의 제곱에 비례하다. 예를 들어, 버블 정렬과 같은 단순 정렬 알고리즘은 이차 시간 복잡도를 가진다.
- 삼차 시간 복잡도 (O(n^3)): 알고리즘의 실행 시간이 입력 크기의 세제곱에 비례하다. 주로 삼중 루프를 사용하는 알고리즘에서 나타난다.
- 지수 시간 복잡도 (O(2^n)): 알고리즘의 실행 시간이 입력 크기의 지수 함수에 비례하다. 예를 들어, 완전 탐색 문제에서 지수 시간 복잡도가 나타날 수 있다.
- 팩토리얼 시간 복잡도 (O(n!)): 알고리즘의 실행 시간이 입력 크기의 팩토리얼 함수에 비례하다. 주로 순열을 생성하거나 검토하는 문제에서 나타난다.
1. O(1) - 상수 시간 복잡도
예시: 배열의 특정 인덱스에 접근하기
public class Main {
public static int getElement(int[] arr, int index) {
return arr[index];
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int index = 2;
System.out.println(getElement(arr, index)); // Output: 3
}
}
위의 getElement 메서드는 배열의 특정 인덱스에 있는 요소를 반환한다. 배열의 크기와 상관없이 항상 일정한 시간 내에 완료된다.
2. O(n) - 선형 시간 복잡도
예시: 배열의 모든 요소를 출력하기
public class Main {
public static void printElements(int[] arr) {
for (int element : arr) {
System.out.println(element);
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
printElements(arr);
}
}
printElements 메서드는 배열의 모든 요소를 한 번씩 출력한다. 배열의 크기가 두 배가 되면 출력하는 데 걸리는 시간도 두 배가 된다.
3. O(n^2) - 이차 시간 복잡도
예시: 버블 정렬
public class Main {
public static 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;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
버블 정렬 알고리즘은 두 개의 중첩된 반복문을 사용하여 배열을 정렬한다. 배열의 크기가 두 배가 되면 작업의 수는 약 네 배가 된다.
4. O(log n) - 로그 시간 복잡도
예시: 이진 탐색
public class Main {
public static 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; // Target not found
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 7;
int result = binarySearch(arr, target);
System.out.println(result); // Output: 6
}
}
이진 탐색 알고리즘은 정렬된 배열에서 목표 값을 찾기 위해 배열을 절반씩 나누어 가며 검색한다. 배열의 크기가 두 배가 되면 비교 횟수는 한 번 증가한다.
5. O(n log n) - 선형 로그 시간 복잡도
예시: 합병 정렬
public class Main {
public static void mergeSort(int[] arr) {
if (arr.length < 2) {
return;
}
int mid = arr.length / 2;
int[] left = new int[mid];
int[] right = new int[arr.length - mid];
System.arraycopy(arr, 0, left, 0, mid);
System.arraycopy(arr, mid, right, 0, arr.length - mid);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
합병 정렬 알고리즘은 배열을 재귀적으로 나누고, 각 부분을 정렬하여 합치는 방식으로 작동한다. 이 과정에서 배열의 크기와 로그의 곱만큼 시간이 소요된다.
이 예시들은 Java에서 시간 복잡도를 어떻게 표현할 수 있는지를 보여준다. 각 알고리즘의 시간 복잡도는 문제의 입력 크기와 알고리즘의 실행 시간 간의 관계를 나타낸다.