¿Algoritmos para calcular la mediana en funcionamiento?

Question

En los tamaños de ventana más pequeños, n log n la clasificación podría funcionar. ¿Hay algún algoritmo mejor para conseguirlo?

Answer 1

Es una mala forma de ordenar una matriz para calcular una mediana. Las medianas (y otros cuantiles) se calculan normalmente utilizando la función quickselect algoritmo, con $O(n)$ complejidad.

También puede consultar mi respuesta a una pregunta reciente relacionada con este tema aquí .

Answer 2

Aquí es un artículo que describe un posible algoritmo. Incluye el código fuente y una aplicación bastante seria (detección de ondas gravitacionales basada en interferometría láser), por lo que se puede esperar que esté bien probado.

Answer 3

Si estás dispuesto a tolerar una aproximación, hay otros métodos. Por ejemplo, una aproximación es un valor cuyo rango está dentro de cierta distancia (especificada por el usuario) de la verdadera mediana. Por ejemplo, la mediana tiene un rango (normalizado) de 0,5, y si especifica un término de error del 10%, querrá una respuesta que tenga un rango entre 0,45 y 0,55.

Si esa respuesta es adecuada, hay muchas soluciones que pueden funcionar con ventanas deslizantes de datos. La idea básica es mantener una muestra de los datos de cierto tamaño (aproximadamente 1/término de error) y calcular la mediana en esta muestra. Se puede demostrar que con alta probabilidad, independientemente de la naturaleza de la entrada, la mediana resultante satisface las propiedades que he mencionado anteriormente.

Por lo tanto, la cuestión principal es cómo mantener una muestra continua de los datos de un cierto tamaño, y hay muchos enfoques para ello, incluyendo la técnica conocida como muestreo de depósito. Por ejemplo, en este trabajo: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136

Answer 4

Si mantienes una ventana de datos de longitud-k como una lista doblemente enlazada ordenada, entonces, mediante una búsqueda binaria (para insertar cada nuevo elemento a medida que se desplaza en la ventana) y una matriz circular de punteros (para localizar inmediatamente los elementos que hay que borrar), cada desplazamiento de la ventana requiere un esfuerzo O(log(k)) para insertar un elemento, sólo O(1) para borrar el elemento desplazado fuera de la ventana, y sólo O(1) para encontrar la mediana (porque cada vez que se inserta o borra un elemento en la lista se puede actualizar un puntero a la mediana en tiempo O(1)). Por lo tanto, el esfuerzo total para procesar una matriz de longitud N es O((n-k)log(k)) <= O(n log(k)). Esto es mejor que cualquiera de los otros métodos propuestos hasta ahora y no es una aproximación, es exacta.

Answer 5

Aquí hay una solución O(1) para encontrar la mediana actual, y O(log n) para añadir un nuevo número http://www.dsalgo.com/RunningMedian.php