시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)
시간 복잡도는 속도에 관한 것이며 공간 복잡도는 메모리 사용량에 관한 것이다. 시간 복잡도는 연산 횟수로 구한다.
데이터의 개수가 n이하는 알고리즘 A가 유리하고 n이상은 알고리즘 B가 유리한것을 확인할 수 있다.
따라서 상황에 맞게 적절한 알고리즘을 택해야 한다. 다음의 코드를 살펴보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <stdio.h>
int LSearch(int arr[], int len, int target) { // Linear Search 함수
for (int i = 0; i < len; i++) {
if (arr[i] == target) // 찾으면 해당 위치의 인덱스 반환
return i;
}
return -1;
}
int main(void) {
int arr[] = { 2, 5, 3, 1, 9 };
int idx;
idx = LSearch(arr, sizeof(arr) / sizeof(int), 9);
if (idx == -1)
printf("탐색 실패\n");
else
printf("타겟 인덱스: %d \n", idx);
idx = LSearch(arr, sizeof(arr) / sizeof(int), 6);
if (idx == -1)
printf("탐색 실패\n");
else
printf("타겟 인덱스: %d \n", idx);
return 0;
}
|
cs |
이 경우 최악의 시간복잡도는 O(N)이다. 최선, 평균, 최악이 있지만 최악을 기준으로 잡는다.
이번에는 이진 탐색(Binary Search)알고리즘을 보자. 순차 탐색에 비해 좋은 성능을 내지만 정렬이 되어있어야 한다는 제약 조건이 존재한다.
이진탐색 (Binary Search)
이진탐색을 먼저 그림으로 나타내면 다음과 같다.
이진탐색의 코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <stdio.h>
int BSearch(int arr[], int len, int target) {
int first = 0;
int last = len - 1;
int mid;
while (first <= last) { // fist와 last가 뒤집어지면 종료
mid = (first + last) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] > target) // 중간 값이 target보다 큰 경우
last = mid - 1; // mid 좌측에서 탐색 진행
else // 중간 값이 target보다 작은 경우
first = mid + 1;
}
return -1; // 탐색하지 못한 경우
}
int main(void) {
int arr[] = { 1, 3, 5, 7, 9, 11 };
int idx;
idx = BSearch(arr, sizeof(arr) / sizeof(int), 7);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 인덱스 위치: %d \n", idx);
idx = BSearch(arr, sizeof(arr) / sizeof(int), 8);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 인덱스 위치: %d \n", idx);
return 0;
}
|
cs |
이 경우 최악의 시간 복잡도는 O(logN)이다.
각 빅 - 오 표기법들의 성능 비교
각 빅-오 표기법들의 성능은 다음과 같다.
순서대로 O(1) < O(logN) < O(N) < O(NlogN) < O(𝑁^2) < O(2^N) < O(N!) 이다.
'자료구조' 카테고리의 다른 글
| 5. 스택 (0) | 2022.01.10 |
|---|---|
| 4. 연결 리스트 (0) | 2021.07.19 |
| 3. 배열 기반 리스트 (0) | 2021.07.19 |
| 2. 재귀 (Recursion) (0) | 2021.06.27 |