배열에서 i번째 큰 원소 찾기 문제

선택 문제

임의로 나열된 n개의 데이터에서 크기가 i번째인 것을 찾기

• i=1 : 최소치 문제

• i=n : 최대치 문제

  → 이 둘은 $O(n)$의 복잡도를 가짐

이 외의 일반적인 경우에는 정렬 후 i번째 원소를 선택하게 되어있다.

⇒ $O(n\log(n))$ : 일반적인 정렬 알고리즘의 시간복잡도

최솟값 찾기 $O(n)$

같은 방식으로 최댓값 찾기도 할 수 있겠죠?

int Minumum (int A[], int n){
	/* 입력A[] : n개의 숫자 저장된 배열
				 n : 배열 A에 저장되어 있는 숫자 개수
		 출력 : A에 저장된 값 중 최솟값 */
	int i, Temp;
	Temp = A[0]; // 맨 첫번째 원소를 Temp에 저장
	for (i=1;i<n;i++)
		if (Temp>A[i]) Temp=A[i]; // A[1]~A[n-1]을 반복하면서, A[i]가 Temp보다 작으면 Temp에 A[i]를 넣음
		// 결과적으로 원소를 하나하나 보면서 비교해서 가장 작은 것을 Temp에 넣게 되는 것
		// O(n)이 걸릴 수 밖에 없다.
	return Temp;
}

최댓값 최솟값 동시에 찾기 $O(n)$

선택 알고리즘(Selection algorithm)

void findMinMax(int A[], int n, int *Minimum,int *Maximum){
	/* 입력 A : n개의 숫자 저장되 배열
		 n : 배열 A에 저장되어 있는 숫자 개수
		 출력 : *Minimum A에 저장된 값 중 최솟값 
						*Maximum A에 저장된 값 중 최댓값 */
	int i;
	int Small, Large;
	*Minimum=A[0]; *Maximum=A[0]; // 일단 처음에는 둘 다 A의 첫번째 원소를 넣어준다
	for(i=1,i<n-1;i+=2){
		if (A[i] < A[i+1])
			{Small=A[i]; Large=A[i+1];}
		else
			{Small=A[i+1]; Large=A[i];}
		if(Small<*Minimum) *Minimum=Small;
		if(Large>*Maximum) *Maximum=Large;
	}
	return;
}

최댓값 찾기와 최솟값 찾기 방법을 사용한 경우와 선택 알고리즘 사용 경우 비교

(1) 최댓값 찾기 + 최솟값 찾기 시간복잡도 : 최댓값 찾기는 n-1회 비교, 최솟값 찾기는 찾은 최댓값을 제외해 n-2회 비교 : $2n-3$

(2) 선택알고리즘 :

이 방법은 주어진 배열의 요소를 2개씩 묶어 묶음 별로 최대와 최소를 구하는 것이다. (요소가 두개니까 최대 최소라기보다는 더 큰 값, 더 작은 값이겠다 ㅎㅎ)

https://hini7.tistory.com/122

이렇게 모인 큰 값끼리 비교하고, 작은 값끼리 비교하는 방법이라고 볼 수 있다.

$\frac{n-1}{2}$회 반복하고 그 내에서 3번을 비교하게 되므로