최악의 경우 선형시간 선택
-
최악의 경우 선형시간 선택 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 29. 13:38
최악의 경우 선형시간 선택 최악의 경우에도 선택 알고리즘의 수행 시간이 Θ(n)이 되는 것을 보장하는 선택 알고리즘이다. 최악의 경우 선형시간 선택 알고리즘 분할 알고리즘으로 배열을 n개 씩의 그룹으로 나누고 그룹의 중간 값들의 중간 값을 이용해 선택 알고리즘을 수행한다. 최악의 경우 선형시간 선택 알고리즘 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을 기준 원소로..