1. 시간복잡도와 공간 복잡도란?
시간 복잡도 - 시간 복잡도란 주어진 문제를 해결하기 위한 연산횟수를 말한다.
공간복잡도 - 알고리즘이나 프로그램이 실행되는 동안 사용하는 메모리의 공간의 크기를 의미한다.
2. 시간 복잡도 표기법
시간 복잡도는 아래와 같이 3가지의 표기법이 존재하지만 주로 사용되는 표기법은 빅-오(BigO-notation)표기법을 사용하여 표현한다. 왜냐면 수행 시간을 계산할 때 worst case를 기준으로 만족하는 수행 시간을 계산하기 위해서이다.
- 빅-오메가(best case) : 최선일 때의 연산 횟수를 나타낸 표기법
- 빅-세타(average case) : 보통일 때의 연산 횟수를 나타낸 표기법
- 빅-오 (worst case) : 최악일 때의 연산 횟수를 나타낸 표기법
알고리즘의 최악의 경우를 고려함으로써 예상치 못한 상황에서도 안정적인 성능을 보장하기 위해서 최악의 경우에도 효율적으로 동작하는 알고리즘을 고민하기위해서이다.
일반적인 BigO 표기법
O(1): 상수 시간 복잡도. 입력 크기에 상관없이 일정한 실행 시간을 갖는 경우.
public class ConstantTimeExample {
public static int constantTimeExample(int[] arr) {
return arr[0];
}
}
O(log n): 로그 시간 복잡도. 주로 이진 검색과 같은 알고리즘 등의 경우
이는 보통 이진 탐색과 같은 알고리즘에서 볼 수 있는데
레벨 0: 8
/ \
레벨 1: 3 10
/ \ / \
레벨 2: 1 6 9 14
/ \
레벨 3: 4 7위와 같은 이진 트리에서 탐색을 한다고 할 때
루트 노드에서 첫번째 자식 노드 층으로 이동하게 되면 탐색해야할 노드가 절반으로 줄어들게 된다.
만약 탐색을 해야할 자료의 개수가 2^n개 라면 n번의 탐색을 통해서 원하는 값을 찾을 수 있게되고
이를 수식으로 나타내면
따라서 이를 O(log n)으로 표기한다.
public class BinarySearch {
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;
}
}
O(n): 선형 시간 복잡도. 입력 크기에 비례하는 선형적인 실행 시간을 갖는 경우.
public class LinearTimeExample {
public static void linearTimeExample(int[] arr) {
for (int element : arr) {
System.out.println(element);
}
}
}
O(n log n): 선형 로그 시간 복잡도. 효율적인 정렬 알고리즘 등의 같은 경우
병합정렬에서는 배열을 반으로 나눈후, 나눠진 각각을 재귀적으로 정렬한 뒤 병합하는과정을 거친다.
이는 정렬해야하는 데이터의 크기(n)에 크기(n)만큼의 로그(log n)를 곱한만큼의 시간이 소요된다.
public class MergeSort {
public static void mergeSort(int[] arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int n1 = mid - low + 1;
int n2 = high - mid;
int[] left = new int[n1];
int[] right = new int[n2];
for (int i = 0; i < n1; ++i) {
left[i] = arr[low + i];
}
for (int j = 0; j < n2; ++j) {
right[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = low;
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < n1) {
arr[k++] = left[i++];
}
while (j < n2) {
arr[k++] = right[j++];
}
}
}
O(n^2): 이차 시간 복잡도. 중첩된 반복문이 있는 알고리즘의 경우
public class BubbleSort {
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+1] and arr[i]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
O(2^n): 지수 시간 복잡도. 재귀적 알고리즘 중 부분 집합 생성 등의 경우
public class ExponentialTimeExample {
public static int recursiveExponential(int n) {
if (n <= 1) {
return n;
}
return recursiveExponential(n - 1) + recursiveExponential(n - 2);
}
}