entendimiento "mediana de las medianas" algoritmo

Question

quiero entender "mediana de las medianas" algoritmo en el siguiente ejemplo:

Hemos 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 clasificar cada grupo (en este caso que ya están ordenados)

2. Segundo paso de forma recursiva, fi nd el "verdadero" mediana de las medianas (50 45 40 35 30 25 20 15 10), es decir el conjunto será divididos en 2 grupos:

   50 25 
   
   45 20 
   
   40 15 
   
   35 10 
   
   30 
   

   clasificación de estos 2 grupos

   30 10 
   
   35 15 
   
   40 20 
   
   45 25 
   
   50 
   

las medianas es de 40 y 15 (en caso de que los números son aún tomamos dejaron mediana) por lo que el valor devuelto es 15, sin embargo "verdadero" mediana de las medianas (50 45 40 35 30 25 20 15 10) es 30, por otra parte, hay 5 elementos menos 15 que son mucho menos del 30% de 45 que se mencionan en wikipedia

y por lo tanto T(n) <= T(n/5) + T(7n/10) + O(n) falla.

Por cierto, en el ejemplo Wikipedia, me sale como resultado de la recursividad 36. Sin embargo, el verdadero promedio es de 47.

Por lo tanto, creo que en algunos casos esto puede no volver recursividad cierto mediana de las medianas. Quiero entender dónde está mi error.

Answer 1

El problema está en el paso donde dices para encontrar la mediana verdadera de las medianas. En su ejemplo, que tenía estas medianas:

50 45 40 35 30 25 20 15 10 

El verdadero medio de este conjunto de datos es 30, no 15. Usted no encuentra este medio mediante el fraccionamiento de los grupos en bloques de cinco y teniendo la mediana de los medianas, pero en lugar de llamar recursivamente el algoritmo de selección en este grupo más pequeño. El error en la lógica está asumiendo que la mediana de este grupo se encuentra mediante la división de la secuencia anterior en dos bloques

50 45 40 35 30 

y

25 20 15 10 

luego encontrar la mediana de cada bloque. En cambio, el algoritmo de la mediana de las medianas se llamará recursivamente a sí mismo en el conjunto completo de datos 50 45 40 35 30 25 20 15 10. Internamente, esto dividirá el grupo en bloques de cinco y los clasificará, 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 en el 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 obtiene una muy buena división según sea necesario.

Espero que esto ayude!

Answer 2

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

He agregado comentarios al código para obtener una 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 su ejemplo:

La mediana de la función de las medianas se llamará sobre toda la gama 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 M = select({x[i]}, n/10) se llama, array {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 selección de llamada función será M = select({50 45 40 35 30 20 15 10}, 4)

2. La segunda vez M = select({x[i]}, n/10) se llama, array {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, llegando al punto en el que tenía una duda, ahora dividimos la matriz L alrededor de M = 20 con k = 4.
   
   Recordar matriz L aquí es: 50 45 40 35 30 20 15 10.
   
   La matriz se divide en L1, L2 y L3 según las reglas L1 < M, L2 = M y L3 > M. Por lo tanto:
   L1: 10 15
L2: 20
L3: 30 35 40 45 50
   
   Desde k = 4, es mayor que length(L1) + length(L2) = 3. Por lo tanto, la búsqueda se continuó 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, M = 30 serán recibidos en la primera select llamada de función a través de toda la matriz de 45 elementos, y la misma lógica de partición que separa la matriz L alrededor M = 30 se aplicará para obtener finalmente la mediana de las medianas.

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