[공학]최대값 및 최소값 알고리즘

소개글

컴퓨터 알고리즘 분할 및 정복 단원에서 다루는 최대값 및 최소값 알고리즘 분석

목차

1. 최대값 및 최소값 문제 소개
2. 알고리즘 : 순차적 찾기 알고리즘
3. 알고리즘 : 1차원 배열에서 최대값 및 최소값
4. 위의 두 알고리즘의 복잡도 비교

본문내용

제 3장 분할 및 정복

3.4 최대값 및 최소값 문제

1. 최대값 빛 최소값 문제 소개
분할 및 정복에 의해서 쉽게 풀 수 있는 또 다른 문제에는 n개의 원소로 구성된 리스트에서 최대값 및 최소값을 찾는 문제가 있다.
먼저 분할 및 정복에 의하지 않고 순차적인 비교에 의해 최대값 및 최소값을 구하는 알고리즘을 분석하고, 분할 및 정복에 의해 최대값 및 최소값을 구하는 알고리즘을 분석하여 그 둘의 복잡도를 비교한다.

2. 알고리즘 3.3 : 순차적 찾기 알고리즘
1) 알고리즘 3.3
문제 : 1차원 배열(리스트)에서 최소값 및 최대값 구하기.
입력 : 자연수 n 및 1차원 배열(리스트) A
출력 : A의 최소값 min 및 최대값 max

Void seq_maxmin (intmax, int min)
{
int i, n;
max = A[1];
min = A[1];
for (i=2; i<=n; i++){
if (A[i] > max) max = A[i];
if (A[i] < min) min = A[i];
}
}
2) 알고리즘 3.3 풀이
위의 알고리즘에서 n이 의미하는 것은 행렬의 크기이다. n의 값을 2로 놓고, 위의 알고리즘을 풀이 해 보겠다.
9개의 원소를 가지는 1차원 배열에서 최대값 및 최소값을 구한다.
A : 인덱스
1
2
3
4
5
6
7
8
9
원소의 값
10
4
3
0
6
20
9
12
18

max = 10, min = 10, i = 2, n = 9 일 때,
알고리즘 수행 후, max = 10, min = 4이 된다.
max = 10, min = 4, i = 3, n = 9 일 때,
알고리즘 수행 후, max = 10, min = 2이 된다.
.
.
.
위와 같은 방법으로 알고리즘은 8번 수행하게 되고, 최대값 max에는 20, 최소값 min에는 0이 들어가게 된다.

참고 자료

없음