Explicación del algoritmo Median of Medians

Question

El enfoque Median of medians es muy popular en los algoritmos de partición tipo quicksort para proporcionar un pivote bastante bueno, de modo que particione uniformemente el conjunto. Su lógica se da en Wikipedia como:

El pivote elegido es menor y mayor que la mitad de los elementos en la lista de medianas, que es alrededor de n/10 elementos (1/2 * (n/5))) para cada mitad. Cada uno de estos elementos es una mediana de 5, por lo que es menos de 2 elementos y más de 2 elementos más fuera del bloque. Por lo tanto, el pivote tiene menos de 3 (n/10) elementos fuera del bloque y más de 3 elementos (n/10) fuera del bloque. Por lo tanto, la mediana elegida divide los elementos en algún lugar entre 30%/70% y 70%/30%, lo que asegura el peor comportamiento lineal del algoritmo.

¿Alguien puede explicarlo un poco lúcidamente para mí? Me resulta difícil entender la lógica.

Answer 1

Piense en el siguiente conjunto de números:

5 2 6 3 1 

La mediana de estos números es 3. Ahora si tiene un número n, si es n > 3, entonces es más grande que al menos la mitad de los números anteriores. Si es n < 3, entonces es más pequeño que al menos la mitad de los números anteriores.

Así que esa es la idea. Es decir, para cada conjunto de 5 números, obtienes su mediana. Ahora tiene números n/5. Esto es obvio

Ahora, si obtiene la mediana de esos números (llámelo m), es más grande que la mitad de ellos y más pequeño que la otra mitad (¡por definición de mediana!). En otras palabras, m es más grande que n/10 números (que a su vez eran medianas de pequeños grupos de 5 elementos) y más grande que otros n/10 números (que de nuevo eran medianas de pequeños grupos de 5 elementos).

En el ejemplo anterior, hemos visto que si la mediana es k y tiene m > k, entonces m es también más grande que otros 2 números (que ellos mismos eran más pequeños que k). Esto significa que para cada uno de esos 5 grupos de elementos más pequeños donde m era más grande que su medio, m es más grande también que otros dos números. Esto lo convierte en al menos 3 números (2 números + la mediana misma) en cada uno de esos n/10 pequeños grupos de 5 elementos, que son más pequeños que m. Por lo tanto, m es al menos más grande que 3n/10 números.

Lógica similar para el número de elementos m es mayor que.

Answer 2

Explicación de la mediana - de - las medianas algoritmo para encontrar el mayor entero k-ésima de n también se puede encontrar aquí: http://cs.indstate.edu/~spitla/presentation.pdf