- 시간복잡도와 공간복잡도에 대해 설명해 주세요.
- 시간복잡도(Time Complexity): 알고리즘이 실행을 완료하는 데 걸리는 시간을 입력 크기에 대한 함수로 나타낸 것입니다.
- 공간복잡도(Space Complexity): 알고리즘이 실행되는 동안 필요한 메모리 공간의 양을 입력 크기에 대한 함수로 나타낸 것입니다.
시간복잡도
O(1)
배열에서 특정 인덱스의 요소에 접근하는 경우
입력 크기와 무관하게 항상 일정한 시간이 소요되므로 O(1)입니다.
int[] array = {1, 2, 3, 4, 5};
int element = array[2]; // O(1) 시간복잡도O(n)
배열의 모든 요소의 합을 구하는 경우
배열의 크기가 n일 때, for 루프는 n번 실행되므로 시간복잡도는 O(n)
int[] array = {1, 2, 3, 4, 5};
int sum = 0;
for (int i = 0; i < array.length; i++) {
sum += array[i];
}O(n^2)
배열 내 모든 쌍의 요소를 출력하는 경우
중첩된 for 루프가 각각 n번씩 실행되므로 전체 실행 횟수는 n * n = n^2이며, 따라서 시간복잡도는 O(n^2)입니다.
int[] array = {1, 2, 3, 4, 5};
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
System.out.println(array[i] + ", " + array[j]);
}
}O(log n)
이진 탐색 알고리즘을 사용하는 경우.
이진 탐색은 배열을 반씩 나누어 탐색하므로, 시간복잡도는 O(log n)입니다.
int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid;
} else if (array[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 요소를 찾지 못함
}공간복잡도
O(1)
추가적인 메모리 공간을 거의 사용하지 않는 경우.
입력 크기와 무관하게 항상 일정한 크기의 메모리만 사용하므로 공간복잡도는 O(1)
public int hi(int[] array) {
return array[0] + array[1];
}O(n) 공간복잡도
입력 크기에 비례하여 추가적인 메모리 공간을 사용하는 경우.
원본 배열과 동일한 크기의 배열을 생성하므로, 공간복잡도는 O(n)
public int[] hi(int[] array) {
int[] copy = new int[array.length];
for (int i = 0; i < array.length; i++) {
copy[i] = array[i];
}
return copy;
}Big-O, Big-Theta, Big-Omega에 대해 설명해 주세요.
- 알고리즘의 시간 복잡도와 공간 복잡도를 수학적으로 표현하는 데 사용되는 점근 표기법입니다.
Big-O 표기법
- 알고리즘의 최악의 경우 실행 시간 또는 공간 사용량의 상한선을 나타냅니다.
public void hi(int n) {
for (int i = 0; i < n; i++) { // O(n)
for (int j = 0; j < n; j++) { // O(n)
System.out.println(i + ", " + j);
}
}
}중첩된 두 개의 for 루프는 각각 n번씩 실행되므로 전체 반복 횟수는 n^2
시간 복잡도는 O(n2)
Big-Omega 표기법 (Ω)
- 알고리즘의 최선의 경우 실행 시간 또는 공간 사용량의 하한선을 나타냅니다.
public void hi(int n) {
for (int i = 0; i < n; i++) { // Ω(n)
System.out.println(i);
}
}설명: 이 함수는 최소한 n 번의 반복을 필요로 하므로, Ω(n)의 시간 복잡도를 가집니다.
Big-Theta 표기법 (Θ)
- 알고리즘의 실행 시간 또는 공간 사용량의 상한선과 하한선이 동일한 경우를 나타냅니다.
예시
public void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quickSort(array, low, pivotIndex - 1);
quickSort(array, pivotIndex + 1, high);
}
}퀵 정렬의 평균 시간 복잡도는 Θ(n log n)입니다.
이는 최선과 최악의 경우 모두 n log n에 비례하는 시간이 소요된다는 것입니다.
public void hi(int n) {
if (n == 0) {
System.out.println("n is zero"); // O(1)
} else {
for (int i = 0; i < n; i++) { // O(n)
System.out.println(i);
}
}
}- Big-O: 최악의 경우에 기반하여 O(n)의 시간 복잡도를 가집니다.
- Big-Omega: 최선의 경우에 기반하여 Ω(1)의 시간 복잡도를 가집니다.
6.2 Big-Theta의 예시
for (int i = 0; i < n; i++) { // O(n)
System.out.println(i);
}- 이 함수는 최선, 최악, 평균 모두에서 n번의 반복을 수행하므로, Θ(n) 입니다.
- 다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?
- Big-O 표기법을 주로 사용하는 이유는 알고리즘의 최악의 경우 성능을 보수적으로 평가하고, 알고리즘의 상한선만 고려하여 계산과 이해가 용이하며, 널리 사용되는 표준이기 때문입니다.
- O(1)은 O(N²)보다 무조건적으로 빠른가요?
아뇨!!!
빅 오(Big O) 표기법은 알고리즘의 입력 크기 ( N )가 매우 클 때의 성장률을 나타내며, 상수 계수나 낮은 차수의 항은 무시합니다. 따라서 실제 실행 시간은 알고리즘의 상수 계수와 입력 크기에 따라 달라질 수 있습니다.
알고리즘 문제 풀 시, 시간 복잡도 제한
시간 제한 1초 인 경우
- N의 범위가 500 경우 O(N^3)
- N의 범위가 2,000 경우 O(N^2)
- N의 범위가 100,000 O(n log n)
- N의 범위가 10,000,000 O(N)
알고리즘 테스트에서 공간 복잡도를 고려할 때, 메모리 제한이 512 MB라면 어느 정도까지의 공간 복잡도를 사용할 수 있는지에 대해 설명해 드리겠습니다.
알고리즘 문제 풀 시, 공간 복잡도 제한
- 메모리 제한이 512 MB라면, 알고리즘이 사용하는 모든 변수, 데이터 구조, 함수 호출 스택 등이 이 제한 내에 있어야 합니다.
| 데이터 타입 | 크기 |
|---|---|
| boolean | 1 byte |
| byte | 1 byte |
| char | 2 bytes |
| short | 2 bytes |
| int | 4 bytes |
| float | 4 bytes |
| long | 8 bytes |
| double | 8 bytes |
| 객체 참조 | 4 bytes (32비트), 8 bytes (64비트) |
-
1차원 배열
int[] arr = new int[N];
메모리 사용량:N * 4 bytes -
2차원 배열**
int[][] arr = new int[N][N];
메모리 사용량:N X N X 4 bytes
최대 크기
-
O(N) 공간 복잡도일 경우
- int형 배열을 사용할 때:
- 최대
N은 약 1억 (10^8)까지 가능 - 메모리 사용량:
10^8 * 4 bytes = 400 MB
-
O(N log N) 공간 복잡도
N은 10^7 이하
-
O(N^2) 공간 복잡도
- 2차원 배열을 사용할 때:
- 최대
N은 약 1만 (10,000) 정도 - 메모리 사용량:
10,000 * 10,000 * 4 bytes = 400 MB
