Download Mediana y estadisticas de orden

Medianas y Estadísticas de Orden
Agustín J. González
ELO320: Estructura de Datos y Algoritmos
1 er. Sem. 2004
1
Conceptos





La estadística de orden i-ésimo de un conjunto de n
elementos es el elemento i-ésimo más pequeño.
El mínimo es la estadística de primer orden.
La mediana es el punto en la “mitad del camino”
La mediana se ubicas en i=  (n+1)/2  e
i=(n+1)/2
Problema de selección:
Entrada: un conjunto de n números y un número i
1<= i <= n
Salida: El elemento x tal que es mayor que
exactamente otros i-1.
2
Mínimo y máximo




Mínimo(A)
min = A[1;
for (i=2; i<=length(A); i++)
if (min > A[i )
min = A[i;
Puede ser hecho en tiempo (n).
¿Cómo encontramos el i-ésimo lugar de un
conjunto?
Ejercicio: ¿Cuántas veces se ejecuta la asignación
del mínimo?
3
Ejercicio: Número de Asignaciones de
Máximo












El siguiente programa determina el máximo valor en un arreglo no ordenado A[1..n].
max = -"infinito";
for (i=1; i <=n; i++) {
if (A[i] > max)
max = A[i]; /* linea 4 */
Se desea determinar el número promedio de veces que la asignación de la línea 4 es ejecutada.
Suponga que los números en A fueron tomados aleatoriamente del intervalo [0,1].
Si un número x es aleatoriamente escogido dentro de un conjunto de n número distintos, ¿cuál
es la probabilidad que x sea el mayor número del conjunto?

1/n
Cuando la línea 4 es ejecutada, ¿cuál es la relación entre A[i] y A[j] para 1 <=j <= i?

A[i] > A[j]
Para cada i en el rango 1 <= i <=n, ¿cuál es la probabilidad que la línea 4 sea ejecutada?

1/i
Sea s1,s2,..,sn variables aleatorias, donde si representa el número de veces (0 ó 1) que la línea
4 es ejecutada durante la i-ésima iteración. ¿Cuál es el valor esperado E[si]?

E[si] = 0*P(que línea 4 no sea ejecutada) + 1*P(línea 4 sí sea ejecutada) = 1/i
Determine el valor esperado para el número total de veces que la línea 4 es ejecutada.

E[número de veces pedido] = E[s1+s2+s3+...+sn] =
E[s1]+E[s2]+...+E[sn]=1+1/2+1/3+...+1/n
Como nota interesante (fuera del certamen) 1+1/2+1/3+...+1/n =(lg n).
4
( ) Método integral para acotar
sumatorias
1
1 2
n 1
 1 x dx  ln( x)
1
n 1
 ln( n  1) <
1
n
1 / i
<
i 1
1 
n 1
2
1
( x  1)
n 1
dx  1  ln( x  1) 2  1  ln( n)
5
Problema de selección



Problema de selección: Basta usar una forma adaptada de
Quicksort o Randomized_Quicksort. En ésta sólo nos
preocupamos de donde se encuentra la estadística del orden
que buscamos.
Randomized_Select(A, p,r,i)
if (p==r)
return A[p;
q = Randomized_Partition(A,p,r);
k = q -p+1;
if (i <= k)
return Randomized_Select(A,p,q,i);
else
return Randomized_Select(A, q+1, r, i-k);
El tiempo de este algoritmo es (n) en promedio y su peor
caso es (n2).
6
Divertimento



Lu
Una fábrica de aspirinas tiene 7 depósitos con
aspirinas de 100 mg correspondientes a la
producción de cada día de una semana.
El generente de producción fue notificado que
durante un día de la semana las aspirinas resultaron
de 110 mg.
Usando una pesa sólo una vez, ¿Cómo puede
determinar el depósito con las aspirinas defectuosas?
Ma
Mi
Ju
Vi
Sa
Do
7