# i 번째 작은 값 찾기 ## 학습 목표 - 평균 선형시간 선택 알고리즘의 원리 이해 - 최악 선형시간 선택 알고리즘의 원리 이해 ## 목차 --- 1. 정렬 후 찾기 2. quick selection 알고리즘 3. linear selection 알고리즘 4. 수행시간 분석 5. quick selection 알고리즘 개선 ## 1. 정렬 후 찾기 - O(n log n) ## 2. quick selection --- quick sort 의 partition을 이용한 선택 평균 O(n), 최악 O(n^2) ## 3. linear selection 최악의 경우에도 O(n)으로 만들자. 등비수열로 partition이 나뉘어진다면 O(n)으로 줄일 수 있다