¿Cuál es la mejor manera de hacer un seguimiento de la mediana?

8

Leí una pregunta y estoy buscando información sobre cómo resolverla:

  

Los números se generan aleatoriamente y se almacenan en una matriz (en expansión). ¿Cómo realizarías un seguimiento de la mediana?

Hay dos estructuras de datos que pueden resolver el problema. Uno es el árbol binario equilibrado, el otro son dos montones que mantienen el rastro de la mitad más grande y la mitad más pequeña de los elementos. Creo que estas dos soluciones tienen el mismo tiempo de ejecución que O(n lg n) , pero no estoy seguro de mi criterio.

¿Cuál es la mejor manera de hacer un seguimiento de la mediana?

Mi intento:

En esta pregunta, creo que un montón es la mejor manera de realizar un seguimiento de la mediana. Hay dos montones, el montón grande y el montón pequeño, que no tienen que ser secuenciales. Primero, calculamos el valor medio de los elementos de la matriz. Si el elemento es menor que el valor medio, colocamos el número en el montón pequeño. Por el contrario, ponemos el número al gran montón. Si el número de la pila grande es igual a la cantidad de la pila pequeña, la mediana es la más grande en la pila pequeña y la más pequeña en la pila grande. Si los dos montones tienen un tamaño diferente, simplemente extraemos el elemento raíz del montón con un tamaño más grande y lo empujamos a la raíz del montón de tamaño más pequeño. Para el montón grande, el elemento raíz es el más pequeño, y para el montón pequeño, el elemento raíz es el más grande. De esta manera, si los dos montones tienen el mismo tamaño o una diferencia digital, encontramos el medio en la raíz.

Creo que esta solución tiene el tiempo de ejecución como O (m * n), m significa las veces que ajustamos los montones de desequilibrio.

¿Es esta la mejor manera de hacer un seguimiento de la mediana?

    
pregunta Steven Mou 28.06.2011 - 17:37

3 respuestas

1

Probablemente hay más de 2 estructuras de datos que resuelven este problema. Eche un vistazo a Medianas aproximadas y otros Quantiles en un pase y con memoria limitada

No usan dos montones. Me imagino que podría modificar su algoritmo para obtener periódicamente un valor aproximado de la mediana de ejecución. Por supuesto, la buena aproximación dependería de muchos factores, uno de los cuales es la cantidad de datos que ha pasado a través del algoritmo.

    
respondido por el Bruce Ediger 29.06.2011 - 19:39
0

Una mejor solución es utilizar una lista de omisión. Dado que la lista en la que se insertará se mantiene siempre como una lista ordenada (por el hecho mismo de cómo la está creando), la complejidad de la inserción es O (log n). Aprovechará el hecho de que la primera inserción le proporciona la mediana a un costo cero (el elemento insertado es la mediana). Después de cada inserción adicional, su lista aún está ordenada, y la mediana en sí se desplazará hacia arriba o hacia abajo en un solo índice, y esta comparación es O (1).

Complejidad total = O (log n)

    
respondido por el Michael Hays 29.06.2011 - 17:55
0

De hecho, puede encontrar la mediana en O (n) operaciones solo al encontrar el número más pequeño de k th en una lista, :) busque en Median of Medians. algoritmo de selección para más detalles.

    
respondido por el Ruslan Kabalin 17.07.2011 - 21:39

Lea otras preguntas en las etiquetas