tendencia sacar saca resueltos para moda medidas mediana estadistica ejemplos datos como central calculo calcular aritmetica agrupados algorithm median

algorithm - sacar - media mediana y moda para datos no agrupados



Algoritmo O(n) para encontrar la mediana de una colección de números (3)

Problema: la entrada es una secuencia (no necesariamente clasificada) S = k1, k2, ..., kn de n números arbitrarios. Considere la colección C de n² números de la forma min {ki, kj}, para 1 <= i, j <= n. Presente un algoritmo O(n) time y O(n) space para encontrar la mediana de C.

Hasta ahora he encontrado al examinar C para diferentes conjuntos S que el número de instancias del número más pequeño en S en C es igual a (2n-1), el siguiente número más pequeño: (2n-3) y así sucesivamente hasta que solo tiene una instancia del mayor número.

¿Hay alguna manera de usar esta información para encontrar la mediana de C?

Hay un numero de posibilidades. Uno que me gusta es el algoritmo de Hoare''s Select . La idea básica es similar a una Quicksort, excepto que cuando recurse, solo recurse en la partición que contendrá los números que está buscando.

Por ejemplo, si quieres la mediana de 100 números, comenzarías por particionar la matriz, al igual que en Quicksort. Tendrás dos particiones, una de las cuales contiene el 50º elemento. Realiza recursivamente tu selección en esa partición. Continúe hasta que su partición contenga solo un elemento, que será la mediana (y tenga en cuenta que puede hacer lo mismo con otro elemento de su elección).

Sí, buen acertijo. Podemos encontrar la mediana de desarrollo en las líneas que usted dijo.

En C tenemos 1 ocurrencia de max (k), 3 ocurrencia de siguiente más alta, 5 de siguiente más alta y así sucesivamente

  1. Si pedimos elementos de C, el número de elementos a la izquierda del mth número más alto es m ^ 2 (suma de números impares)

  2. Los números que nos interesan (para calcular la mediana) a. Si n es impar, es (n ^ 2 + 1) / 2 = alfa b. Si n es par, entonces alpha1 = n ^ 2/2 y alpha2 = n ^ 2/2 + 1 pero alpha1 = n ^ 2/2 nunca es un número cuadrado => el número inmediatamente a la derecha de alpha1 es igual a alpha1 ( la suma de los primeros m números impares es cuadrada) => alpha1 = alpha2.

  3. Entonces, todo se reduce a la determinación de m, de modo que m ^ 2 (suma de los primeros números impares) es simplemente mayor que (n ^ 2/2)

  4. Por lo tanto, se reduce a determinar m = techo (n / sqrt (2) y mth número más alto en la secuencia original. (Si se busca mth más alto o (nm-1) el más bajo es la optimización).

  5. Podemos encontrar fácilmente el mth número más alto (solo sigamos notando el primer número más grande desde la izquierda) o usar la mediana del algortitmo de las medianas para hacerlo en tiempo lineal.