중간 알고리즘 이해의 중간 값

Question

나는 웹을 검색하고 중간 알고리즘의 중앙값에 대한 위키 페이지를 방문했다. 하지만 내 질문에 대한 명확한 진술을 찾을 수없는 것 같습니다.

매우 큰 정수 목록 (TB)이 있고 분산 방식으로이 목록의 중간 값을 찾으려면 다양한 크기의 하위 목록에 나열 (또는 같음은 중요하지 않음) 한 다음 작은 하위 목록의 중앙값을 계산 한 다음 중간 값의 중앙값을 계산하면 원래 큰 목록의 중앙값이 계산됩니까?

또한이 문장은 k 번째 통계에도 맞습니까? 이 분야의 연구 등에 대한 링크에 관심이 있습니다.

Answer 1

귀하의 질문에 대한 답변은 '아니오'입니다.

병렬 설정에서 k 주문 통계 (물론 중간 값 포함)를 실제로 선택하는 방법을 알고 싶다면 (분산 설정은 실제로 다르지 않습니다.)이 최근의 문서를 살펴보십시오 다섯 방법을 사용하여 이러한 선회 주위

여기 Deterministic parallel selection algorithms on coarse-grained multicomputers

, 우리는 피벗으로이 가중 3 중앙값을 사용하고, 파티션 :있는 나는 새로운 병렬 선택을위한 예술 알고리즘의 이전 상태를 개선하는 알고리즘을 제안 파티셔닝. 우리는 또한 MPI를 사용하여 알고리즘을 구현하고 테스트했다. 결과는 매우 양호하며 최악의 경우 O (n) 선택 알고리즘을 이용하는 결정 론적 알고리즘이라는 점을 감안하면 매우 좋습니다. 무작위로 사용하기 O (n) QuickSelect 알고리즘은 매우 빠른 병렬 알고리즘을 제공합니다.

Answer 2

매우 큰 정수 목록 (TB)이 있고 분산 방식으로이 목록의 중간 값을 찾으려면 목록을 다양한 크기의 하위 목록으로 나눕니다 (또는 동등하지 않습니다 정말로 중요하지 않음), 그 작은 하위 목록의 중앙값을 계산 한 다음 중간 값의 중앙값을 계산하면 원래 큰 목록의 중간 값이됩니다.

아니요. 전체 목록의 실제 중간 값은 반드시 모든 하위 목록의 중앙값이 아닙니다.

median-of-median은 무작위로 선택한 요소보다 실제 중간 값에 가까워 빠른 선택을위한 피벗 선택이 가능하지만 실제 중간 값을 찾으려면 나머지 quickselect 알고리즘을 수행해야합니다 큰 목록의.