algorithm - para - mediana estadistica ejemplos

¿Cómo puedo encontrar la mediana de los números en tiempo lineal usando montones?

Question

Wikipedia dice:

Algoritmos de selección: Encontrar el mínimo, máximo, tanto el mínimo como el máximo, la mediana , o incluso el k-ésimo elemento más grande se puede hacer en tiempo lineal usando montones.

Todo lo que dice es que se puede hacer, y no cómo.

¿Me puede dar un comienzo sobre cómo se puede hacer esto usando montones?

Answer 1

Almacene el primer entero en la matriz y establezca un contador en 1. Luego recorra los números enteros restantes en el vector. Si el entero actual en la matriz es el mismo que el almacenado, el contador se incrementa en uno, de lo contrario, el contador se reduce en uno. Si el contador alguna vez llega a cero, tira el entero almacenado y reemplázalo con el número entero actual en la matriz. Cuando finalmente has recorrido todos los enteros, te queda un candidato. Luego debe recorrer nuevamente la matriz y contar la ocurrencia del candidato para verificar que esto realmente sea un dominador.

static int FindDominator(int[] arr)
{
int counter = 1;
int candidate = arr[0];
for(int i = 1; i < n; i++)
{
if(arr[i] == candidate) counter++
else
{
counter--;
if(counter == 0) { candidate = arr[i]; counter = 1; }
}
}
counter = 0;
for(int i = 0; i < n; i++)
{
if(arr[i] == candidate) counter++;
}
if(counter > n / 2) return candidate;
else return -1;
}

Answer 2

Es probable que haya algoritmos mejores, pero así es como lo haría:

Tiene dos cubos y un valor. El valor es la mediana, los dos segmentos son "más grandes que la mediana" y "más pequeños que la mediana". Para cada elemento x en la matriz, reequilibre los big_bucket tal manera que big_bucket y small_bucket difieran en no más de 1 en su tamaño. Al mover objetos del cubo grande al cubo pequeño, primero deben atravesar el valor mediano para llegar allí (es decir, una diferencia de 2 empujará con éxito un elemento de un cubo al siguiente; una diferencia de 1 empujará un elemento de una cubeta al valor mediano.) Al final de su primer pase a través de la matriz, el valor debe ser su mediana.

Answer 3

Obviamente, min y max en O (n) es fácil y no requiere un montón.

El K''th más grande se puede hacer de manera bastante simple manteniendo hasta el momento un montón de k de los valores k más altos. El tiempo de ejecución sería O (n * logk). Podría llamar a ese tiempo lineal si k es de tamaño fijo yk << n.

No creo que la mediana sea posible. Solo crear un montón de tamaño O (n) requiere O (n * logn) tiempo.

Edit: Ok, después de pensar en esto un poco más, IVlad tiene razón. Puede crear un montón en O (n), para un tamaño fijo. Pero ... eso no ayuda al OP con su pregunta mediana. La técnica de creación de pila lineal solo produce un montón válido como salida final. El enfoque simple de hacer n inserciones, que resulta en un montón válido después de cada paso es O (n * logn).

Me parece que usar montones para encontrar la mediana requeriría el uso de aquellos que ejecutan sub-montones. Por ejemplo, hubo una respuesta publicada aquí (que parece que se eliminó ahora) que vinculaba a una publicación de blog que sugería un algoritmo para este problema. Rastreó la mediana de carrera usando dos montones (la mitad más pequeña y la mitad más grande) mientras hacía un solo pase a través de los datos. Eso requeriría un enfoque más lento e ingenuo, ya que depende de mantener montones válidos a medida que los inserta y quita de ellos.

¿Hay alguna otra forma de encontrar la mediana usando la técnica lineal de creación de un solo disparo?

Answer 4

Utilizaría un montón de min-max-mediana para encontrar el mínimo, el máximo y la mediana en tiempo constante (y tómese tiempo lineal para construir el montón). Puede usar árboles de estadísticas de orden para encontrar el k-ésimo valor más pequeño / más grande. Ambas estructuras de datos se describen en este documento sobre min-max montones [pdf link] . Los montones Min-Max son montones binarios que se alternan entre min-heaps y max-mont.

Del documento: Un montón de min-max-median es un montón binario con las siguientes propiedades:

1) La mediana de todos los elementos se encuentra en la raíz

2) El subárbol izquierdo de la raíz es un montón mínimo-máximo Hl de techo de tamaño [((n-1) / 2)] que contiene elementos menores o iguales a la mediana. El subárbol derecho es un montón máximo-mínimo Hr de piso de piso [((n-1) / 2)] que contiene solo elementos mayores que o iguales a la mediana.

El documento continúa para explicar cómo construir tal montón.

Editar: Al leer el documento más a fondo, parece que si se crean los montículos min-max-mediana se necesita encontrar primero la mediana (FTA: "Encontrar la mediana de todos los n elementos usando cualquiera de los algoritmos conocidos de tiempo lineal") . Dicho esto, una vez que hayas creado el montón, puedes mantener la mediana simplemente manteniendo el equilibrio entre el montón mínimo-máximo a la izquierda y el montón máximo-mínimo a la derecha. DeleteMedian reemplaza la raíz con el mínimo del montón máximo-mínimo o el máximo del montón mínimo-máximo (lo que mantiene el equilibrio).

Entonces, si planeas utilizar un montón de min-max-mediana para encontrar la mediana de un conjunto de datos fijo, eres SOL, pero si lo estás utilizando en un conjunto de datos cambiantes, es posible.

Answer 5

Vea esta página de wikipedia en algoritmos de selección . En particular, observe el algoritmo BFPRT y el algoritmo Median of Medians. BFPRT es probabilísticamente lineal, y se modela en quicksort; La mediana de Medians está garantizada de forma lineal, pero tiene un gran factor constante, por lo que puede llevar más tiempo en la práctica, dependiendo del tamaño de su conjunto de datos.

Si solo tiene unos pocos cientos o miles de elementos para seleccionar la mediana, sospecho que es más fácil una rápida guía rápida seguida de una indexación directa.

Answer 6

si conoce más sobre la estructura de datos de montón, entenderá fácilmente que ese es realmente el caso. la estructura del montón se puede construir en el tiempo O (n), hay montón mínimo y montón máximo. El elemento raíz min montón le dará el elemento más pequeño. El elemento raíz máximo del montón le dará el elemento máximo. Solo construyendo el montón encuentras el mínimo y máximo. la misma idea para la mediana y la k-ésima más grande, mientras construyes tu montón, puedes encontrar la mediana y la k-ésima más grandes mirando la rama izquierda o derecha del árbol y manteniendo una cantidad constante de memoria para almacenar el número del elemento. etc.

Answer 7

tal vez no existía cuando se formuló la pregunta original, pero ahora wiki tiene un enlace a la fuente, y aquí está: http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf

específicamente, vaya a la página 17 y mire la descripción de RSEL4. Demuestran en el teorema 3.2 que la complejidad temporal de este algoritmo de selección k-ésima es O (k). entonces te llevaría O (n) construir el montón, y un O (k) extra para encontrar el artículo k-ésimo más pequeño.

no es tan sencillo como algunas de las otras respuestas han sugerido