중간 값 선택 알고리즘 - 절대 평균값 또는 절대 값 중앙값에 가까운 "중앙값의 중앙값"을 찾습니다.

Question

CLRS 제 3 판의 "최악의 선형 시간의 선택"에서는 목록의 중앙값을 찾기위한 "선택"알고리즘 (Blum, Floyd, Pratt, Rivest 및 Tarjan으로 인해 BFPRT 알고리즘이라고도 함)에 대해 설명합니다. 최악의 경우 O (n) 시간. 화이트 보드에서 샘플을 실행하려고하면 약간 혼란 스럽습니다. 나는 "Select"에 대한 호출마다 특정 수의 요소를 제거 할 수 있다는 것을 이해합니다. (30 %는 다시 읽어야하는 반면 70 %는 다시 검사해야 함), 어떤 부분이 혼란 스럽습니까? 즉, 배열이 높이 5와 너비 n/5 인 행렬로 시각화되면 제거 된 요소는 어느 사분면에 놓이게됩니까? 원래 그것이 대각선으로 인접한 두 사분면이라고 생각했지만 지금은 중앙값의 중간 값에 따라 단 하나의 사분면이라고 생각하고 있습니다 (단계 5, 6 및 7 참조) here.

그래서 위키피디아에 가서 CLRS보다 적은 분석으로 빠른 설명이 있는지 살펴 보았습니다 (분석을 위해 CLRS로 다시 뛰어 오기 전에 알고리즘을 이해하기 위해). 나는 this에 왔는데, 특히 '마침내 중앙값의 중간 값'이 피봇으로 선택되었습니다. " 위키 피 디아에있는 설명의 소리에서 "선택"은 중간 값 인 진정한 중앙값을 찾지 못합니다 - 퀵 소트의 피봇 선택에 충분합니다.

그렇다면 "선택"은 진정한 중간 값의 관점에서 무엇을합니까? 이 모든 것을 생각해내는 구절은 "부분적 계층 구조"입니다. 이해하는 바와 같이 "선택"이 작동하지만,이 논리의 일부분만으로이 부분 계층 구조에 기반한 중앙값이되는 요소를 제거 할 수 있습니까?

Answer 1

절대 중간 값을 찾습니다.

당신이 말했듯이, "선택"은 중앙값 인 요소보다는 진정한 중앙값을 찾지 않습니다 - 퀵 소트 용 피봇 선택에 충분합니다. 특히 모든 반복에서 데이터 집합의 30 % 이상을 삭제할 수있는 평균값입니다. 불행히도 이것은 또한 값 비싼 작업입니다.

핵심 아이디어는 중간 값의 중간 값이 중간 값이 5 이하인 요소 중 3 개보다 작거나 같은 것입니다. 따라서 5 개 그룹의 절반에 대해 5 개 요소 중 3 개 이하이므로 집합의 30 % 이상이 5 개 요소보다 작거나 같습니다. 따라서 데이터 세트의 최대 70 %에 있습니다.

마찬가지로 데이터 세트의 최소 70 %입니다.

이렇게하면 극단적 인 값을 갖는 피벗 점을 선택하는 잠재적 인 quickselect의 위험을 피할 수 있습니다.

효율성과 최악의 경우를 결합하려면 quickselect와 결합하면됩니다. 예를 들어 4 라운드의 quickselect와 1 라운드의 quickselect, 4 라운드의 quickselect 등이 있습니다. BFPRT의 값 비싼 라운드는 O(n)을 보증하지만 quickselect는 평균 속도가 빠릅니다. 몇 차례의 quickselect를 수행 할 때까지 BFPRT의 첫 번째 라운드를 연기하면 추가 실행 시간을 평균 quickselect보다 몇 % 더 늘릴 수 있습니다. (최악의 경우 비용이 많이 들지만, 그 문제가 발생할 것으로 예상하지는 않습니다.)