선택문제란 ?

선택문제

n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제

 

원래라면 단순하게 최소 숫자를 k번 찾거나(Okn), 숫자들을 정렬한 후 K번째 숫자를 찾는다.(Onlogn)

이진탐색으로는 ? 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교하면서, 입력을 1/2로 나눈 두 부분 중 한 부분만을 검색한다.

 

선택문제는 입력이 정렬되어 있지 않으므로, 입력 숫자들 중에서 (퀵정렬과 같이) 피봇을 선택하여 분할한다.

분할하고 알아야 하는 것은 Small 그룹(피봇보다 작은 숫자그룹)과 Large 그룹(피봇보다 큰 숫자그룹)의 크기(숫자의 개수)이다.

- Small 그룹에서 k번째 작은 숫자가 속한 경우 => k번째 작은 숫자를 Small 그룹에서 찾는다.

- Large 그룹에서 k번째 작은 숫자가 속한 경우 => (k - |Small 그룹 크기| - 1) 번째로 작은 숫자를 Large 그룹에서 찾는다. (여기서 뺀 1은 피봇이다)

*Small 그룹 크기 S = (p-1) - left + 1 

 

평균 시간 복잡도 : O(n)

입력 크기가 n에서부터 3/4배로 연속적으로 감소되고, 크기가 1일 때에는 더 이상 분할할 수 없다.

 

이진탐색과의 유사성 비교

- 이진탐색은 분할과정을 진행하면서 범위를 1/2씩 좁혀가며 찾고자 하는 숫자를 탐색한다

- 선택알고리즘은 피봇으로 분할하여 범위를 조혀간다.

- 부분문제들을 취합하는 과정이 별도로 필요없다. (분할하고 버리기 때문)