OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Mediana y estadísticos de orden ======

Dado un multiconjunto((Es decir, puede tener repetidos.)) de $n$ valores, se le llama //estadístico de orden $k$// al $k$-ésimo elemento más chico. Así, el estadístico de orden 1 es el mínimo elemento, el estadístico de orden 2 es el mínimo elemento entre los que quedan si se borra un elemento mínimo, y así siguiendo, de modo que el estadístico de orden $n$ será simplemente el máximo.

Al estadístico de orden $\frac{n-1}{2}$ se lo llama **mediana**, y este es especialmente importante ya que separa a los demás valores en "dos partes" iguales: Exactamente $\frac{n-1}{2}$ valores menores o iguales que la mediana, y $\frac{n-1}{2}$ mayores o iguales que la mediana. Si $n$ es par, la mediana no puede partir en dos conjuntos exactamente iguales, así que interesan los estadísticos de orden $\frac{n}{2}$ y $\frac{n}{2}+1$, que son "los dos elementos centrales". Según el contexto para el cual queramos utilizarla, la mediana en este caso se suele considerar como uno de estos dos valores, o como el promedio de ambos, o como cualquier valor entre uno y otro inclusive. 

Es fácil calcular un cierto estadístico de orden [[algoritmos-oia:ordenamiento|ordenando]] todos los elementos: una vez que tenemos los elementos en un arreglo ordenado, para cada posición $i$ (contando desde 1) se encuentra allí el estadístico de orden $i$. Esto podría tomar en el caso general $O(N \lg N)$ comparaciones, pero calcula todos los estadísticos de orden.

Sin embargo, si buscamos **un solo** estadístico de orden particular, es posible encontrarlo en $O(N)$, ya que no hace falta ordenar **todo** el arreglo. En particular, la mediana de un conjunto puede encontrarse con $O(N)$ comparaciones.

FIXME: Algoritmo lineal para el cálculo de un estadístico de orden [probabilístico de tipo Las Vegas, salvo adversario maléfico On-Line, el determinista es peor]. La explicación de "Selection" está en el Cormen.

==== Propiedad útil de la mediana y los estadísticos de orden ====

Supongamos que tenemos una larga ruta, con $n$ pueblos en ciertas posiciones. Tenemos que elegir una posición de la ruta para crear allí una oficina de correos, de modo tal que **el total** de lo que se debe viajar desde cada pueblo hasta la oficina de correos sea lo menor posible.

El total es justamente la suma, sobre todos los pueblos, de la distancia entre el pueblo y la oficina. Más precisamente, si el pueblo $i$ está en el kilómetro $p_i$ de la ruta, y ubicamos la oficina de correos en $x$, entonces el total de kilómetros de viaje será $\sum_{i=1}^n{|p_i - x|}$. Lo que buscamos es el $x$ que minimice esta cuenta.

Como ejemplo de [[algoritmos-oia:busqueda-ternaria|búsqueda ternaria]], vimos que la función anterior resulta ser convexa y por lo tanto unimodal, así que con búsqueda binaria o ternaria se puede encontrar el valor mínimo y el kilómetro óptimo (valor de $x$) donde ubicar la oficina.

Sin embargo, es posible dar una solución más elegante, que permite entender mejor lo que está pasando y que a veces es más útil para razonar o para resolver problemas más complejos: resulta que el valor óptimo de $x$ es **la mediana** ((Si $n$ es par, cualquier valor entre los dos elementos del medio, inclusive, produce un total óptimo.)). La explicación se basa en el dibujo interactivo que se puede ver [[https://www.xarg.org/2016/07/calculate-the-argmin-of-the-sum-of-absolute-values/|aquí]]. Como la distancia total es la suma de las "barritas" desde $x$ hasta los puntos, cuando hay más barritas de un lado que del otro, es posible bajar la distancia total moviendo $x$ en esa dirección. Por lo tanto, necesariamente el mejor valor posible tendrá que tener igual cantidad barritas saliendo hacia cada lado, para que no se puede mejorar moviendo $x$. Y eso ocurre cuando $x$ es la mediana de los puntos $p_i$.

== Problemas relacionados a la mediana ==

Un problema relacionado con esta última idea (pero que involucra más que solamente eso) es el problema [[http://www.ioinformatics.org/locations/ioi00/contest/day2/post/post.pdf|Post Office]] de la IOI 2003.

Otro problema relacionado con la mediana en esa misma IOI es [[http://www.ioinformatics.org/locations/ioi00/contest/day1/median/median.pdf|Median Strength]]

== Variante con pesos ==

Una variante de la misma idea puede ocurrir cuando los "pueblos" tienen un peso $w_i$ (podría ser su cantidad de habitantes), de forma que nos interesa optimizar $\sum_{i=1}^n{w_i|p_i - x|}$. En este caso, lo que notamos es que la cuenta es la misma que en el problema normal sin pesos, si tuviéramos $w_i$ copias del pueblo $p_i$((Si bien esta "idea" se basa en que los pesos $w_i$ sean enteros, la conclusión sigue siendo válida con pesos reales positivos.)). Entonces, el lugar óptimo es la "mediana de los pesos", es decir, la posición de aquel pueblo que reparta los pesos totales a izquierda y derecha lo más parejo posible.

== Variante asimétrica ==

Otros estadísticos de orden nos darían el óptimo, en lugar de la mediana, si trabajamos con una distancia "asimétrica". Por ejemplo, supongamos que la ruta está sobre la ladera de una montaña, y a medida que avanzan los kilómetros en la ruta, esta siempre asciende la montaña. De esta forma, es natural considerar más costosos los recorridos subiendo que los recorridos bajando. Si suponemos que solo nos interesa analizar el costo para los viajes del pueblo a la oficina de correos y no el de la vuelta((Quizás, porque los pueblos envían muchas cartas al exterior pero casi no reciben cartas, y lo que queremos es que poder enviar las cartas urgentes desde los pueblos hasta la oficina sea lo más rápido posible, pero luego de entregada la carta, el tiempo para volver al pueblo no se considera importante porque la carta urgente ya fue entregada.)), la "distancia" entre un pueblo $p_i$ y la oficina de correos será $p_i-x$, si $ x \leq p_i$, o bien $C(x-p_i)$ si $p_i \leq x$, siendo $C$ un factor de costo "adicional" por subir la montaña.

La mediana da el óptimo con $C=1$. Para otros valores de $C$, por el mismo argumento de analizar cómo cambia el costo al mover $x$, el óptimo se alcanzará cuando hacia arriba haya $C$ veces la cantidad de pueblos que hacia abajo, pues si no fuera así, mover $x$ en una de las dos direcciones reduce el costo total. Esto significa que el $x$ óptimo es el pueblo que deja $\frac{n}{1+C}$ pueblos a su izquierda, es decir, el estadístico de orden $\frac{n}{1+C}$ entre las posiciones de los pueblos.
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
