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 haría 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 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 necesitan ser secuenciales. Primero, calculamos el valor medio de los elementos en la matriz. Si el elemento es menor que el valor medio, colocamos el num en el montón pequeño. Por el contrario, ponemos el num al gran montón. Si el número del montón grande es igual al número del montón pequeño, el mayor en el montón pequeño y el más pequeño en el montón grande son la mediana. Si los dos montones tienen un tamaño diferente, simplemente sacamos 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,
Creo que esta solución tiene el tiempo de ejecución como O (m * n), m significa los tiempos que ajustamos los montones de desequilibrio.
¿Es esta la mejor manera de hacer un seguimiento de la mediana?
fuente
std::nth_elementalguien?Respuestas:
Probablemente hay más de 2 estructuras de datos que resuelven este problema. Eche un vistazo a las medianas aproximadas y otros cuantiles en un solo paso y con memoria limitada
No usan dos montones. Me imagino que podría modificar su algoritmo para obtener periódicamente un valor aproximado aproximado de mediana. La buena aproximación, por supuesto, dependerá de muchos factores, entre los cuales se encuentra la cantidad de datos que han pasado a través del algoritmo.
fuente
Una mejor solución es usar una lista de omisión. Dado que la lista en la que insertará siempre se mantiene como una lista ordenada (por el solo hecho de cómo la está construyendo), la complejidad de la inserción es O (log n). Aprovecharás el hecho de que la primera inserción te proporciona la mediana a un costo cero (el elemento insertado es la mediana). Después de cada inserción adicional, su lista todavía está ordenada, y la mediana misma se desplazará hacia arriba o hacia abajo por un solo índice, y esta comparación es O (1).
Complejidad total = O (log n)
fuente
O(log n)- insertar n elementos tiene una complejidad deO(n log n)De hecho, puede encontrar la mediana en las operaciones O (n) solo al encontrar el késimo número más pequeño en una lista, :) busque detalles en el algoritmo de selección de la mediana de las medianas .
fuente