Encuentra mediana de matriz sin clasificar en

Para encontrar la mediana de una matriz no ordenada, podemos hacer un montón mínimo en tiempo para elementos, y luego podemos extraer uno por uno elementos para obtener la mediana. Pero este enfoque llevaría tiempo . $O(n\log n)$ $n$ $n/2$ $O(n \log n)$

¿Podemos hacer lo mismo por algún método en tiempo? Si podemos, ¿cómo? $O(n)$

algorithms time-complexity Luv
fuente

en.wikipedia.org/wiki/Selection_algorithm

Jukka Suomela

@JukkaSuomela ¿Por qué no hacer que esta sea una respuesta rápida y simple (con una breve explicación de uno de estos algoritmos, idealmente)?

Raphael

Tenga en cuenta la meta discusión relacionada ; Como resultado, simples búsquedas en la web conducen a la respuesta a esta pregunta.

Raphael

stackoverflow.com/questions/2571358/median-of-a-billion-numbers

Evgeny

Respuestas:

Este es un caso especial de un algoritmo de selección que se puede encontrar el -ésimo elemento más pequeño de una matriz con es la media del tamaño de la matriz. Hay una implementación que es lineal en el peor de los casos. $k$ $k$

Algoritmo de selección genérico

En primer lugar vamos a ver un algoritmo find-kthque encuentra el -ésimo elemento más pequeño de una matriz: $k$

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

La función split(A, pivot)devuelve L,Rtal que todos los elementos en Rson mayores que pivoty Ltodos los demás (menos una aparición de pivot). Entonces todo se hace de forma recursiva.

Esto es en promedio pero en el peor de los casos. $O(n)$ $O(n^2)$

El peor caso lineal: el algoritmo de mediana de medianas

Un mejor pivote es la mediana de todas las medianas de subconjuntos Ade tamaño 5, al llamar al procedimiento en el conjunto de estas medianas.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

Esto garantiza en todos los casos. No es tan obvio. Estas diapositivas de PowerPoint son útiles tanto para explicar el algoritmo como para la complejidad. $O(n)$

Tenga en cuenta que la mayoría de las veces el uso de un pivote aleatorio es más rápido.

jmad
fuente

¿Es este tamaño 5estándar? ¿Qué pasa si el tamaño de A es menor que 5?

Jayesh

Para cualquier n fijo, la complejidad es constante, a menos que sea infinita. Por lo tanto, puede usar cualquier algoritmo válido con complejidad finita para ese caso especial, incluso si fue O (2 ^ n). Para un n fijo (es decir, como máximo 4 en nuestro caso), la complejidad es como máximo O (2 ^ 4) = O (1).

v6ak

En el primer algoritmo: return A[k]es incorrecto (a menos que Ase ordene lo que haría que el algoritmo sea discutible). Si splitsucedió dividir de Atal manera que k = |L| + 1todavía no sabes dónde está el kelemento th. Su caso base es cuando |A| = 1aún necesita hacer una de las dos llamadas recursivas.

wcochran

@NickCaplinger solucionado con web.archive.org

jmad

¿No es el peor caso para el algoritmo de selección genérico O (NlogN)? Incluso si la llamada recursiva deja solo el 10% de la matriz después de cada llamada, sigue siendo un logaritmo en base 10.

octaviano

$n^{-1/4}$ $O(n)$

La idea principal del algoritmo es utilizar el muestreo. Tenemos que encontrar dos elementos que estén muy juntos en el orden ordenado de la matriz y que tengan la mediana entre ellos. Vea la referencia [MU2017] para una discusión completa.

[MU2017] Michael Mitzenmacher y Eli Upfal. "Probabilidad e informática: aleatorización y técnicas probabilísticas en algoritmos y análisis de datos", capítulo 3, páginas 57-62. Cambridge University Press, segunda edición, 2017.

zdm
fuente