중앙값의 중앙값

Question

선형 통계량 O (n)의 크기 n의 배열에서 k 번째로 작은 (또는 가장 큰) 요소를 찾기 위해 주문 통계를 읽었습니다.

는 중간 값의 평균을 찾을 필요가 한 단계가있다.

1. [n/5] 부분으로 배열을 분할합니다. 각 부분에는 5 개의 요소가 있습니다.
2. 각 부분의 중앙값을 찾습니다. (현재 숫자가 [n/5]입니다.)
3. 마지막 번호 만있을 때까지 1 단계와 2 단계를 반복하십시오. (즉 재귀 적)

T (n/5) + O (n) 그리고 T (n) = O (n)을 얻을 수있다.

그러나 우리가 마침내 얻는 수는 중간 값의 중앙값이 아니라 중앙값의 중앙값의 중앙값의 중앙값입니다.

125 개의 요소가있는 배열을 고려하십시오.

첫째, 25 개 부분으로 분할하고, 우리는 25 명 중간 값을 찾을 수 있습니다. 그런 다음이 25 개의 숫자를 5 부분으로 나누어 5 개의 중앙값을 찾습니다. 마지막으로 중간 값의 중간 값 인 숫자를 얻습니다. (중앙값이 중간이 아님)

내가 신경 쓰는 이유는 중앙값의 중앙값보다 작은 (또는 큰) 요소가 대부분 있음을 이해할 수 있습니다. 그러나 중앙값의 중앙값이 아니라 중간 값의 중앙값의 중앙값이된다면 어떨까요? 더 나쁜 경우에는 피벗보다 작거나 (또는 ​​더 큰) 요소가 적어야합니다. 즉 피벗이 배열의 경계에 더 가깝습니다.

우리는 매우 큰 배열이있는 경우

, 우리는 중간 값의 중간 값의 중간 값의 중간 값의 중간 값의 그것의 중간을 발견했다. 최악의 경우 우리가 찾은 피벗은 여전히 ​​한계에 매우 근접 할 수 있으며이 경우 시간 복잡도는 무엇입니까?

125 개 요소의 데이터 집합을 구성했습니다. 결과는 9입니까?

0.8 0.9 1 inf inf 
1.8 1.9 2 inf inf 
6.8 6.9 7 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

2.8 2.9 3 inf inf 
3.8 3.9 4 inf inf 
7.8 7.9 8 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

4.8 4.9 5 inf inf 
5.8 5.9 6 inf inf 
8.8 8.9 9 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

여기서 inf는 충분히 큰 숫자를 의미합니다.

Answer 1

median of median의 중간 값을 [median of] * = M으로 지정합시다.

첫째, 나는 중간 값 알고리즘의 중간 값은 (좋은 피벗을 선택) 재귀 아니라고 생각합니다. 다음과 같은 알고리즘을 진행한다 :

1. 분할 5
2. 의 그룹의 요소가 중간 값의 중앙값을 찾아 피봇으로 사용할 각각의 그룹
3. 의 중앙값을 찾는다.

중앙값의 중앙값은 3n/10 요소보다 작고 3n/4가 아닌 다른 3n/10 요소보다 커야합니다. 중간 값을 선택한 후 n/5 숫자가 있습니다. 중앙값의 중앙값은 해당 값의 절반보다 크거나 작으며 n/10입니다. 그 수는 각각 중간 값이므로 2 개의 숫자보다 크거나 작아서 2n/10 개의 다른 수를 제공합니다. 이제 총계로 n/10 + 2n/10 = 3n/10을 얻게됩니다.

이

1, 2, 7, inf, inf 
3, 4, 8, inf, inf 
5, 6, 9, inf, inf, 
inf, inf, inf, inf, inf, 
inf, inf, inf, inf, inf. 

그래서 중간 값의 평균이 실제로 9

이 될 것입니다 :

이 예를 들어 데이터 세트에서 5 개의 그룹을 수집하고 자신의 중간 값을 계산 한 후, 두 번째 질문을 해결하기 위해, 우리는 다음과 같은 순서를해야합니다

귀하의 제안 [의 중앙값] * 알고리즘의 실행은 다음과 같습니다 이제

T(n) = O(n * log(n)) 

의 우리가 덜 얼마나 많은 숫자 분석 해보자/이상 M.

• 깊이 1 : 우리는 다음 그룹이 N/5 원소 모두 중앙값을
• 깊이 2 : N/25 요소 모두 중앙값
• ...
• 깊이 I : N/A (5^I)의 모든 요소 중앙값

각 그룹 작/등등 이하/2 개보다 큰 이전 깊이의 원소이며 이전의 깊이보다 큰 2 개 원소 :

합계를 계산하면 우리의 M이 (n * (2^k) + k * n)/((2^k) * (5^k))보다 크거나 작음을 알 수 있습니다. 깊이 = 1 인 경우 중앙값은 3n/10입니다.

이제 깊이를 가정하면 [(N) log_5] 즉, N = 5^K, 우리 얻을 :

5^k 개의 * (K + 2^(K))/(5^K * 2^(K)) -> 1입니다.