[서울대학교 논자시 준비] 알고리즘 : chapter 5 선택 알고리즘

평균 선형 시간 선택 알고리즘 n개의 원소로된 집합에서 최소 원소를 찾기 위해서는 O(n)의 사긴이 필요로한다. 그런데 n개의 원소 중 i번째 작은 원소를 찾기 위해서는 O(n^2) 의 시간이 든다. 정렬을 사용하면 O(nlogn)의 시간으로 단축할 수 있으므로 시간은 O(n)과 O(nlogn) 사이의 시간이 들 것이다. 알고리즘을 사용하면 O(n)의 시간에 확인할 수 있다고 한다. 퀵정렬 알고리즘을 개선하면 평균적으로 선형시간에 i번째 작은 원소를 찾을 수 있게 한다. 알고리즘을 살펴보자. 소스코드 select(A, p, r, i) { if (p=r) then return A[p]; q

2023.08.26