알고리즘 Chapter7. Medians and Order statistics

$i^{th}$ order Statistics

n개 수 집합에서 i번째로 작은 원소 찾기 (i = 0 이면 최솟값, i=n-1 이면 최댓값)
n이 홀수일 때, i = (n-1)/2 중앙값, 짝수일 때 i=$\frac{2}{n}-1$, $\frac{2}{n}$ 이면 중앙값

이번 챕터에서는 i=$\frac{2}{n}-1$ 을 중앙값으로 한다. $\therefore median_i = \lfloor \frac{n-1}{2} \rfloor$
최댓값과 최솟값 구하기

Untitled

#include <iostream>
using namespace std;

int minimum(int* A, int n){
	int min = A[0];
	for(int i = 1; i<n; i++){
		if(min>A[i]){
			min = A[i];
		}
	}
	return min;
}

int main() {
  int A[10] = {9,8,7,5,3,6,4,2,0,1};
  int size = sizeof(A)/sizeof(A[0]);
  int min = minimum(A, size);
  cout<<min;
}

최대값, 최솟값을 동시에 구하려면 2n-2번 비교해야하나?

최댓값 최솟값을 동시에 구하기

n개의 원소들 중 둘 씩 쌍을 지어서 둘 중 큰 수는 max, 작은 수는 min과 비교한다.

Untitled

#include <iostream>
#include <vector>
using namespace std;

typedef struct Point{
	int min_v;
	int max_v;
}Point;

Point min_max(int* A, int n){
	int max = -987654321;
	int min = 987654321;
	int i = 0;

	while(i+2 <= n){
		if(A[i]<A[i+1]){
			if(A[i]<min) min = A[i];
			if(A[i+1]>max) max = A[i+1];
		}
		else{
			if(A[i+1]<min) min = A[i+1];
			if(A[i]>max) max = A[i];
		}
		i = i+2;
	}
	if(n%2 == 1){
		if(A[n-1] < min) min = A[n-1];
		if(A[n-1]> max) max = A[n-1];
	}
	return {min, max}; 
}

int main() {
  int A[10] = {9,8,7,5,3,6,4,2,0,1};
  int size = sizeof(A)/sizeof(A[0]);
  Point result = min_max(A, size);
  cout<<result.min_v<<" "<<result.max_v;
}

n이 짝수일 때 while문 안에서 한 쌍의 수마다 3회 비교가 일어난다. → $\frac{3n}{2}$회
n이 홀수일 때 while문 안에서 n-1개의 수에 대해서 3회 비교가 일어나고 바깥 if문에서 두 번 비교가 일어난다. $→ \frac{3(n-1)}{2} + 2 = \frac{3n+1}{2}$회
수행시간은 O(n)이지만 상세하게는 더 빠름!

두 번째로 작은 값 찾기

n개의 서로 다른 수 중에서 두 번째로 작은 값을 찾기
방법1 : 최솟값을 찾고 최솟값을 제외한 나머지 n-1개의 수들 중에서 다시 최솟값을 찾는다 → 2n-3회 비교가 일어남!
방법2 : 최솟값과 두 번째로 작은 값을 동시에 찾는다 → 최소 n-1회, 최대 2n-3회 비교 일어남. 평균 $\frac{2}{3n}-1$ 회

Untitled