Sé que es posible calcular la media de una lista de números en O (n). Pero, ¿y la mediana? ¿Hay algún algoritmo mejor que ordenar (O (n log n)) y buscar el elemento medio (o la media de dos elementos medios si hay un número par de elementos en la lista)?¿Es posible calcular la mediana de una lista de números mejor que O (n log n)?
Este enlace ha aparecido recientemente en el cálculo de la mediana: http://matpalm.com/median/question.html.
En general, creo que no se puede ir más allá del tiempo O (n log n), pero no tengo ninguna prueba al respecto :). No importa cuánto lo haga paralelo, agregar los resultados en un solo valor requiere al menos log n niveles de ejecución.
He cambiado su respuesta de "O (log n)" a "O (n log n)", que es lo que estaba buscando, creo, dada la pregunta y el resto de su respuesta. – Beska
Si los números son discretos (por ejemplo, números enteros) y hay un número manejable de valores distintos, se puede utilizar un "cubo especie", que es O (N), a continuación, iterar sobre los cubos a la figura cuál balde contiene la mediana. El cálculo completo es O (N) en el tiempo y O (B) en el espacio.
De lo que estás hablando es de selection algorithm, donde k = n/2. Hay un método basado en la misma función de partición utilizada en quicksort que funciona. Se llama, no sorprendentemente, quickselect. Si bien puede, como el quicksort, tener un O (n) peor caso, esto se puede reducir al tiempo lineal utilizando el proper pivot selection.
Parcialmente irrelevante, pero: un consejo rápido sobre cómo encontrar rápidamente respuestas a preguntas básicas comunes como esta en la web.
Cálculo eficiente de la muestra la mediana
A pesar de que la clasificación n elementos toma en general O (n log n) las operaciones, mediante el uso de un algoritmo de "dividir y conquistar" la mediana de n elementos se puede calcular con solo operaciones O (n) (de hecho, siempre se puede encontrar el elemento k-ésimo de una lista de valores con este método; esto se llama selection problem) .
... Hay peor de los casos algoritmos de selección de tiempo lineal. ...
Simplemente por diversión (y quién sabe, puede ser más rápido) hay otro algoritmo de mediana aleatoria, explicado técnicamente en el libro de Mitzenmacher y Upfall. Básicamente, eliges un subconjunto de la lista polinomialmente más pequeño y (con algunos trabajos de lujo) tal que probablemente contenga la mediana real y luego la utilices para encontrar la mediana real. El libro está en google books, y aquí hay un link.Nota: Pude leer las páginas del algorthm, por lo que, suponiendo que los libros de google revelen las mismas páginas para todos, también puedes leerlos.
Es un algoritmo aleatorio s.t. si el encuentra la respuesta, es 100% seguro que es la respuesta correcta (esto se llama estilo Las Vegas). La aleatoriedad surge del tiempo de ejecución --- ocasionalmente (con probabilidad 1/(sqrt (n)), creo) NO PUEDE encontrar la mediana, y debe volver a ejecutarse.
Asintóticamente, es exactamente lineal cuando se tiene en cuenta la posibilidad de falla, es decir, es un poquito menos que lineal, exactamente tal que cuando se tiene en cuenta el número de veces que puede necesitar volver a ejecutarlo, se vuelve lineal.
Nota: No estoy diciendo que esto sea mejor o peor --- ¡Ciertamente no he hecho una comparación del tiempo de ejecución de la vida real entre estos algoritmos! Simplemente estoy presentando un algoritmo adicional que tiene un tiempo de ejecución lineal, pero funciona de una manera significativamente diferente.
¡Cosas interesantes! –
Pruebe el algoritmo aleatorizado, el tamaño de muestreo (por ejemplo, 2000) es independiente del tamaño de datos n, todavía podrá obtener una precisión suficientemente alta (99%). Si necesita una mayor precisión, simplemente aumente el tamaño de muestra. Usar Chernoff bound puede probar la probabilidad bajo un cierto tamaño de muestreo. Escribí un código JavaScript para implementar el algoritmo, no dudes en tomarlo. http://www.sfu.ca/~wpa10
Ese enlace habla sobre una "mediana de medianas", o en otras palabras, una aproximación de la mediana "verdadera". No estoy seguro de que eso es lo que el OP está pidiendo. –
Al usar la selección determinista obtienes la mediana real. Ver aquí: http://en.wikipedia.org/wiki/Selection_algorithm – Anna
Veo que Pesto ya escribió esto. – Anna