algorithm - Entendiendo el algoritmo de "mediana de medianas"

selection median-of-medians

Question

Quiero entender el algoritmo de "mediana de medianas" en el siguiente ejemplo:

Tenemos 45 números distintos divididos en 9 grupos con 5 elementos cada uno.

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. El primer paso es ordenar cada grupo (en este caso, ya están ordenados)

2. Segundo paso recursivamente, encuentre la mediana "verdadera" de las medianas ( 50 45 40 35 30 25 20 15 10 ), es decir, el conjunto se dividirá en 2 grupos:

   50 25
   45 20
   40 15
   35 10
   30

   ordenando estos 2 grupos

   30 10
   35 15
   40 20
   45 25
   50

las medianas son 40 y 15 (en caso de que los números sean iguales, tomamos la mediana izquierda), por lo que el valor devuelto es 15, sin embargo la mediana "verdadera" de las medianas ( 50 45 40 35 30 25 20 15 10 ) es 30, además, hay 5 elementos menos de 15, que son mucho menos del 30% de los 45 que se mencionan en wikipedia

y así T(n) <= T(n/5) + T(7n/10) + O(n) falla.

Por cierto, en el ejemplo de Wikipedia, obtengo un resultado de recursión como 36. Sin embargo, la mediana real es 47.

Entonces, creo que en algunos casos esta recursión puede no devolver la mediana real de las medianas. Quiero entender dónde está mi error.

Answer 1

Aquí está el pseudocode para el algoritmo de la mediana de las medianas (ligeramente modificado para adaptarse a su ejemplo). El pseudocódigo en wikipedia falla al retratar el funcionamiento interno de la selectIdx función selectIdx .

He añadido comentarios al código para su explicación.

// 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
}

Tomando tu ejemplo:

La mediana de la función de las medianas se llamará en todo el conjunto de 45 elementos como (con 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. La primera vez que se llama M = select({x[i]}, n/10) , la matriz {x[i]} contendrá los siguientes números: 50 45 40 35 30 20 15 10 . En esta llamada, n = 45 , y por lo tanto, la llamada a la función de selección será M = select({50 45 40 35 30 20 15 10}, 4)

2. La segunda vez que se llama M = select({x[i]}, n/10) , la matriz {x[i]} contendrá los siguientes números: 40 20 . En esta llamada, n = 9 y, por lo tanto, la llamada será M = select({40 20}, 0) . Esta llamada de selección volverá y asignará el valor M = 20 .
   
   Ahora, al llegar al punto en el que tenía dudas, ahora dividimos la matriz L alrededor de M = 20 con k = 4 .
   
   Recuerde que la matriz L es: 50 45 40 35 30 20 15 10 .
   
   La matriz se dividirá en L1, L2 y L3 acuerdo con las reglas L1 < M , L2 = M y L3 > M Por lo tanto:
   L1: 10 15
L2: 20
L3: 30 35 40 45 50
   
   Como k = 4 , es mayor que la length(L1) + length(L2) = 3 . Por lo tanto, la búsqueda continuará con la siguiente llamada recursiva ahora:
   return select(L3,k-length(L1)-length(L2))
   
   que se traduce en:
   return select({30 35 40 45 50}, 1)
   
   que devolverá 30 como resultado. (dado que L tiene 5 o menos elementos, por lo tanto, devolverá el elemento en kth, es decir, la 1ª posición en la matriz ordenada, que es 30).

Ahora, se recibirá M = 30 en la primera llamada a la función de select en toda la matriz de 45 elementos, y la misma lógica de partición que separa la matriz L alrededor de M = 30 se aplicará para obtener finalmente la mediana de las medianas.

¡Uf! Espero ser lo suficientemente detallado y claro para explicar el algoritmo de la mediana de las medianas.

Answer 2

El problema está en el paso donde dices para encontrar la mediana real de las medianas. En tu ejemplo, tenías estas medianas:

50 45 40 35 30 25 20 15 10

La verdadera mediana de este conjunto de datos es 30, no 15. No se encuentra esta mediana al dividir los grupos en bloques de cinco y al tomar la mediana de esas medianas, sino al recurrir recurrentemente al algoritmo de selección en este grupo más pequeño. El error en tu lógica es asumir que la mediana de este grupo se encuentra dividiendo la secuencia anterior en dos bloques

50 45 40 35 30

y

25 20 15 10

luego encontrar la mediana de cada bloque. En su lugar, el algoritmo de mediana de medianas se llamará a sí mismo en el conjunto de datos completo 50 45 40 35 30 25 20 15 10 . Internamente, esto dividirá el grupo en bloques de cinco y los ordenará, etc., pero lo hace para determinar el punto de partición para el paso de partición, y es en este paso de partición que la llamada recursiva encontrará la mediana verdadera de las medianas , que en este caso será 30. Si usa 30 como la mediana como el paso de partición en el algoritmo original, de hecho obtendrá una muy buena división según sea necesario.

¡Espero que esto ayude!