encontrar la mediana con el mínimo tiempo de una matriz

Question

tengo una serie digamos a = { 1,4,5,6,2,23,4,2}; ahora tengo que encontrar la mediana de la posición de matriz de 2 a 6 (términos totales impares), por lo que lo que he hecho, he tomado a[1] a a[5] en arr[0] a arr[4], luego lo he ordenado y escribo el arr[2] como mediana.

Pero aquí cada vez que estoy ingresando valores de una matriz a otra, para que los valores de mi matriz inicial permanezcan iguales. en segundo lugar, he ordenado, por lo que este procedimiento está tomando prácticamente **time**. Así que quiero saber si hay alguna forma en que pueda hacerlo de manera diferente al less my computation time.

¿Algún sitio web, material para entender, qué y cómo hacer?

Answer 1

Si usted está haciendo varias consultas en la misma matriz a continuación, se puede utilizar un segmento de árbol. En general, se utilizan para hacer consultas de rango mínimo/máximo y de suma de rango, pero puede cambiarlo para hacer la mediana del rango.

Un árbol de segmentos para un conjunto con n intervalos utiliza el almacenamiento O (n log n) y se puede construir en el tiempo O (n log n). Una consulta de rango se puede hacer en O (log n).

Ejemplo de la mediana en el árbol segmento rango:

a construir el árbol de segmento de abajo hacia arriba (actualización de arriba hacia abajo):

    [5] 
     [3]      [7] 
[1,2]  [4]   [6]   [8] 
1  2  3  4  5  6  7  8 

Indices cubiertos por nodo:

    [4] 
     [2]      [6] 
[0,1]  [3]   [5]   [7] 
0  1  2  3  4  5  6  7 

Una consulta para la mediana de los índices de rango 4-6 iría por esta ruta de valores:

    [4] 
          [5] 
0  1  2  3  4  5  6  7 

Haciendo una búsqueda para la mediana, usted sabe la cantidad total de elementos en la consulta (3) y la mediana en ese rango sería el 2º elemento (índice 5). Entonces, básicamente estás haciendo una búsqueda para el primer nodo que contiene ese índice que es un nodo con valores [1,2] (índices 0,1).

Hacer una búsqueda de la mediana de la gama 3-6 es un poco más complicado porque hay que buscar dos índices (4,5) que se encuentran en el mismo nodo.

    [4] 
           [6] 
          [5] 
0  1  2  3  4  5  6  7 

Segment tree

Range minimum query on Segment Tree

Answer 2

Es posible encontrar la mediana sin ordenar en el tiempo O (n); los algoritmos que hacen esto se llaman selection algorithms.

Answer 3

Para encontrar la mediana de una matriz de menos de 9 elementos, creo que la más eficiente es utilizar un algoritmo de ordenación como tipo de inserción. La complejidad es mala, pero para una matriz tan pequeña debido a la k en la complejidad de mejores algoritmos como el quicksort, la ordenación por inserción es muy eficiente. Haga su propio punto de referencia, pero puedo decir que obtendrá mejores resultados con la ordenación por inserción que con el ordenamiento de caparazón o el servicio rápido.

Answer 4

Uso std::nth_element de <algorithm> que es O (N):

nth_element(a, a + size/2, a + size); 
median = a[size/2]; 

Answer 5

Creo que la mejor manera es utilizar la mediana de las medianas algoritmo de contar el mayor elemento k-ésima de una matriz. Puede encontrar la idea general del algoritmo aquí: Median of Medians in Java, en la wikipedia: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm o simplemente navegar en internet. Se pueden realizar algunas mejoras generales durante la implementación (evite la clasificación al elegir la mediana de matrices particulares). Sin embargo, tenga en cuenta que para una matriz de menos de 50 elementos es más eficiente utilizar el género de inserción que la mediana del algoritmo de las medianas.