평균 선형 시간 선택 알고리즘

n개의 원소가 규칙없이 저장된 배열에서 i번째 작은 원소를 찾으려 한다.

 

분할 알고리즘 사용

quick sort에서 사용하는 것 처럼 기준 원소 하나를 고르고 기준 원소보다 작거나 같은 원소는 왼쪽 그룹으로, 큰 원소들은 오른쪽 그룹으로 재배치한다.

이렇게 하면 기준 원소가 전체에서 몇 번째 원소인지를 알 수 있다.

만약 기준 원소가 k번째로 작은 원소라고 해보자. i가 k보다 작다면 왼쪽 그룹에 있을 것이고, 크다면 오른쪽 그룹에 있을 것이다.

 

이를 재귀적으로 호출한다면 어떻게 될까?

 

n개의 원소에서 사용되는 비용을 T(n)이라고 하자.

기준 원소가 전체 집합에서 k번째로 작은 원소라면 두 그룹은 k-1개와 n-k로 나뉜다.

그렇다면 식을 다음과 같이 쓸 수 있다.

 

T(n) ≤ max[T(k-1), T(n-k)] + O(n)

 

이때 k가 1부터 n까지 동일한 확률로 일어난다고 가정하면 평균 시간은 다음과 같다.

글씨를 참 못쓴다..

그러므로 평균적인 경우 T(n) = O(n)이다.

 

그러나 최악의 경우(0:n-1로 분할이 계속되는 경우)는 O(n^2)의 시간이 소요된다.

점화식이 다음과 같기 때문이다.

T(n) = T(n-1) + O(n)

 

 

 

 

 

출처 : 서울대학교 컴퓨터공학부 문병로 교수님 알고리즘 수업