Selection Problem

• 입력 : 리스트에 n개의 수와 1과 n 사이의 자연수 k가 주어진다
• 출력 : k번째로 작은 수 를 찾아 리턴한다
• 목적 : 비교횟수를 되도록 줄인다

상한과 하한

• 상한(upper bound) : 어떠한 값 x가 있고 집합 A의 모든 원소보다 크거나 같을 때, x를 상계라고 한다. 그리고 이러한 상계들의 집합에서 최소원소를 상한이라고 한다.

  알고리즘에서 수행시간의 상한은 최악의 경우에서 문제를 수행하는데 걸리는 시간을 의미.

  즉, 항상 해당 시간 이하로 답을 찾을 수 있다는 것을 내포. 우리가 말하는 점근적 표기법에서 $Big-O$ 표기법이 상한을 나타내는데 사용된다.

• 하한(lower bound) : 어떠한 값 x가 있고 집합 A의 모든 원소보다 작거나 같을 때, x를 상계라고 한다. 그리고 이러한 하계들의 집합에서 최대원소를 하한이라고 한다.

  알고리즘에서 수행시간의 하한은 최선의 경우에서 문제를 수행하는데 걸리는 시간을 의미.

  즉, 답을 찾기 위해선 해당 시간이 필수적이라는 것을 내포. 점근적 표기법에서 $Omega$로 하한을 나타낸다.

상한과 하한 값이 같을 때, $Theta$로 표시하고, 이는 알고리즘이 필요한 만큼만을 비교한다는 뜻이다. ****이러한 알고리즘은 최적 알고리즘이라고 부른다.

가장 큰 수 찾기 (k =n)

가장 단순한 selection 문제

def select(A):
	current_max = A[0]
	for i in range(1, len(A)):
		if current_max < A[i]:
			current_max = A[i]
	return current_max

• 최악의 비교 횟수 : $n - 1$번 ⇒ 상한
• 상한의 비교 횟수보다 더 적게 비교해서 최대 값을 찾을 수 있는가? ⇒ 없다. $n-1$번이 필요한 경우가 존재! ⇒ 하한
• 상한 == 하한 → 최적 알고리즘!

가장 작은 수와 가장 큰 수 찾기 (k = 1, k = n)

1. 알고리즘1

1. 가장 작은 수를 $(n - 1)$ 번의 비교로 찾기