3.3 선택문제
선택문제 :n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제
- 단순 알고리즘
1) 최소 숫자를 k번 찾는다. (최악의 경우, O(kn))
-> 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자 제거
2) 숫자들을 정렬한 후, k번째 숫자를 찾는다. (O(nlogn))
알고리즘
//p.131 12,13번 -eClass 자료실 참고
-
Selection 알고리즘 고려사항
1) Selection 알고리즘은 분할 정복 알고리즘이자 랜덤 알고리즘이다.
-선택 알고리즘의 line 1에서 피봇을 랜덤하게 정하기 때문
2) 피봇이 입력을 너무 한쪽으로 치우치게 분할하면
-> 알고리즘 수행시간이 길어진다. -
평균 경우 시간 복잡도
입력 크기가 ㅜ에서부터 3/4로 연속적으로 감소되고, 크기가 1일 때에는 더이상 분할할 수 없다.
평균 2회에 good 분할이 되므로 2*O(n) = O(n) -
선택 알고리즘과 이진탐색의 비교
[유사성]
1) 이진탐색은 분할과정을 진행하면서 범위를 1/2씩 좁혀가며 찾고자 하는 숫자 탐색
2) 선택 알고리즘은 피봇으로 분할하여 범위를 좁혀감
[공통점]
1) 부분 문제들을 취합하는 과정이 별도로 필요 없다. -
Applications
- 선택 알고리즘은 데이터 분석을 위한 중앙값(median)을 찾는데 활용
