알고리즘...26

최악의 경우 선형시간 선택 알고리즘

최악의 경우에도 원소가 선형적으로 선택되지 않도록 하여 소요 시간이 Θ(n)이 되도록 하기 위한 알고리즘이다.

이를 위해 배열을 5개씩의 그룹으로 나누고 그룹의 중간 값을 이용하여 분할 및 선택을 진행한다.

 

최악의 경우 선형시간 선택 알고리즘

LinearSelect(A[], p, r, i)
{
    1. 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다.
    2. 전체 원소를 5개씩의 원소를 가진 ┌n/5┐개의 그룹으로 나눈다.
    3. 각 그룹에서 중앙값을 찾는다.
    	+ 이렇게 찾은 중앙값들을 m1, m2,..., m┌n/5┐이라 하자.
    4. m1, m2,..., m┌n/5┐들의 중앙값 m을 재귀적으로 구한다.
    5. M을 기준 원소로 삼아 전체 원소를 분할한다.
    6. 분할된 두 그룹 중 적합한 쪽을 선택해 단계 1~6을 재귀적으로 반복한다.
}

 

쉽게 배우는 알고리즘 선택 알고리즘 그림 4-3

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘