"중앙값의 중앙값"알고리즘 이해

"중앙값의 중앙값"알고리즘 이해

---

다음 예제에서 "중앙값의 중앙값"알고리즘을 이해하고 싶습니다.

우리는 각각 5 개의 요소가있는 9 개의 그룹으로 나누어 진 45 개의 고유 번호를 가지고 있습니다.

48 43 38 33 28 23 18 13 8

49 44 39 34 29 24 19 14 9 

50 45 40 35 30 25 20 15 10

51 46 41 36 31 26 21 16 53

52 47 42 37 32 27 22 17 54

1. 첫 번째 단계는 모든 그룹을 정렬하는 것입니다 (이 경우 이미 정렬되어 있음).

2. 두 번째 단계는 재귀 적으로 중앙값 ( 50 45 40 35 30 25 20 15 10) 의 "진정한"중앙값을 찾습니다. 즉, 세트는 두 그룹으로 나뉩니다.

   50 25
   
   45 20 
   
   40 15
   
   35 10
   
   30
   

   이 두 그룹 정렬

   30 10
   
   35 15 
   
   40 20
   
   45 25
   
   50
   

중앙값은 40과 15 (숫자가 왼쪽 중앙값을 취한 경우)이므로 반환 된 값은 15이지만 중앙값의 "참"중앙값 ( 50 45 40 35 30 25 20 15 10)은 30이고, 15보다 적은 5 개 요소가 있으며 이는 30보다 훨씬 작습니다. 위키 백과 에서 언급 된 45 %

그래서 T(n) <= T(n/5) + T(7n/10) + O(n)실패합니다.

그런데 Wikipedia 예제에서 재귀 결과는 36입니다. 그러나 실제 중앙값은 47입니다.

따라서 어떤 경우에는이 재귀가 중앙값의 실제 중앙값을 반환하지 않을 수 있다고 생각합니다. 내 실수가 어디인지 이해하고 싶습니다.

---

문제는 중앙값의 실제 중앙값을 찾으려고 말하는 단계에 있습니다. 귀하의 예에서 다음과 같은 중앙값이 있습니다.

50 45 40 35 30 25 20 15 10

이 데이터 세트의 실제 중앙값은 15가 아니라 30입니다. 그룹을 5 개의 블록으로 분할하고 중앙값의 중앙값을 취함으로써이 중앙값을 찾을 수 없습니다. 대신이 작은 그룹에서 선택 알고리즘을 반복적으로 호출하여이 중앙값을 찾습니다. 논리의 오류는 위의 시퀀스를 두 블록으로 분할하여이 그룹의 중앙값을 찾았다 고 가정합니다.

50 45 40 35 30

과

25 20 15 10

그런 다음 각 블록의 중앙값을 찾습니다. 대신 median-of-medians 알고리즘은 전체 데이터 세트에 대해 자신을 재귀 적으로 호출합니다 50 45 40 35 30 25 20 15 10. 내부적으로는 그룹을 5 개의 블록으로 분할하고 정렬하는 등의 작업을 수행하지만 분할 단계에 대한 분할 지점을 결정하기 위해 수행되며이 분할 단계에서 재귀 호출이 중앙값의 실제 중앙값을 찾습니다. ,이 경우에는 30이됩니다. 원래 알고리즘에서 분할 단계로 30을 중앙값으로 사용하면 실제로 필요에 따라 매우 좋은 분할을 얻을 수 있습니다.

도움이 되었기를 바랍니다!

---

다음은 중앙값 알고리즘 의 의사 코드 입니다 (예에 맞게 약간 수정 됨). 위키피디아의 의사 코드는 selectIdx함수 호출 의 내부 동작을 설명하지 못합니다 .

I've added comments to the code for explanation.

// L is the array on which median of medians needs to be found.
// k is the expected median position. E.g. first select call might look like:
// select (array, N/2), where 'array' is an array of numbers of length N

select(L,k)
{

    if (L has 5 or fewer elements) {
        sort L
        return the element in the kth position
    }

    partition L into subsets S[i] of five elements each
        (there will be n/5 subsets total).

    for (i = 1 to n/5) do
        x[i] = select(S[i],3)

    M = select({x[i]}, n/10)

    // The code to follow ensures that even if M turns out to be the
    // smallest/largest value in the array, we'll get the kth smallest
    // element in the array

    // Partition array into three groups based on their value as
    // compared to median M

    partition L into L1<M, L2=M, L3>M

    // Compare the expected median position k with length of first array L1
    // Run recursive select over the array L1 if k is less than length
    // of array L1
    if (k <= length(L1))
        return select(L1,k)

    // Check if k falls in L3 array. Recurse accordingly
    else if (k > length(L1)+length(L2))
        return select(L3,k-length(L1)-length(L2))

    // Simply return M since k falls in L2
    else return M

}

Taking your example:

The median of medians function will be called over the entire array of 45 elements like (with k = 45/2 = 22):

median = select({48 49 50 51 52 43 44 45 46 47 38 39 40 41 42 33 34 35 36 37 28 29 30 31 32 23 24 25 26 27 18 19 20 21 22 13 14 15 16 17 8 9 10 53 54}, 45/2)

1. The first time M = select({x[i]}, n/10) is called, array {x[i]} will contain the following numbers: 50 45 40 35 30 20 15 10. In this call, n = 45, and hence the select function call will be M = select({50 45 40 35 30 20 15 10}, 4)

2. The second time M = select({x[i]}, n/10) is called, array {x[i]} will contain the following numbers: 40 20. In this call, n = 9 and hence the call will be M = select({40 20}, 0). This select call will return and assign the value M = 20.
   
   Now, coming to the point where you had a doubt, we now partition the array L around M = 20 with k = 4.
   
   Remember array L here is: 50 45 40 35 30 20 15 10.
   
   The array will be partitioned into L1, L2 and L3 according to the rules L1 < M, L2 = M and L3 > M. Hence:
   L1: 10 15
L2: 20
L3: 30 35 40 45 50
   
   Since k = 4, it's greater than length(L1) + length(L2) = 3. Hence, the search will be continued with the following recursive call now:
   return select(L3,k-length(L1)-length(L2))
   
   which translates to:
   return select({30 35 40 45 50}, 1)
   
   which will return 30 as a result. (since L has 5 or fewer elements, hence it'll return the element in kth i.e. 1st position in the sorted array, which is 30).

Now, M = 30 will be received in the first select function call over the entire array of 45 elements, and the same partitioning logic which separates the array L around M = 30 will apply to finally get the median of medians.

Phew! I hope I was verbose and clear enough to explain median of medians algorithm.

ReferenceURL : https://stackoverflow.com/questions/9489061/understanding-median-of-medians-algorithm