Mediana de un arreglo

Encontrar la mediana $z$ de un arreglo $A[1,n]$ (con $n$ impar) es un problema para el cual no se conoce el número exacto de comparaciones. Se conoce una cota inferior de $(2+2^{-50})n$ y una cota superior de $2.95 n$. Mostraremos una cota inferior relativamente sencilla de $\frac{3(n-1)}{2}$ comparaciones. Hablaremos de la mediana $z$ que entregará el algoritmo aunque éste no la conozca hasta el final.

Consideraremos dos tipos de comparaciones, cruciales y no cruciales. Conceptualmente, una comparación resulta crucial para un elemento $x$ si es la que nos permite conocer la relación entre $x$ y $z$. Más precisamente, consideremos la historia de las comparaciones que realizó el algoritmo para determinar $z$, y definamos un grafo con un nodo por elemento. Dibujemos una arista entre $z$ y los elementos $x$ que se compararon directamente contra $z$, roja si $x > z$ y azul si $x < z$. También pintemos a $x$ de rojo o azul, respectivamente. Para todo nodo rojo $x$, dibujemos aristas rojas hacia elementos $y > x$ que aún no tengan color y se hayan comparado directamente contra $x$. Para todo nodo azul $x$, dibujemos aristas azules hacia elementos $y < x$ que aún no tengan color y se hayan comparado directamente contra $x$. En ambos casos, pintemos a $y$ de rojo o azul, respectivamente. Continuemos así hasta pintar todas las aristas y elementos posibles. Todas las aristas pintadas corresponden a las comparaciones cruciales.

El grafo formado por las aristas rojas y azules no tiene ciclos. Si no resulta conexo, el algoritmo no puede conocer la mediana, pues implica que existe un elemento $x$ no pintado, por lo cual el algoritmo nunca hizo una comparación que le permitiera determinar si $x < z$ ó $x > z$. El adversario puede entonces decidir si $x < z$ ó $x > z$, haciendo que la respuesta $z$ sea incorrecta. Por lo tanto, se necesitan al menos $n-1$ comparaciones cruciales.

Mostraremos que, además, el algoritmo debe haber realizado al menos $\frac{n-1}{2}$ comparaciones no cruciales, cuyas aristas no están en el grafo porque resultan ser $x < y$ para un $y > z$, o bien $x > y$ para un $y < z$. Para esto, consideremos un adversario que responde a las comparaciones del algoritmo mediante asignarles valor a los elementos cuando los ve por primera vez. Antes de ello, determinará un valor $z$ para quien será la mediana, sin asignárselo a ningún elemento en particular. Modelaremos el avance del conocimiento del algoritmo partiendo los elementos en tres conjuntos:

• $a$ es el cardinal del conjunto $A$ de los elementos que nunca han sido comparados (no confundir con el arreglo $A$);
• $b$ es el cardinal del conjunto $B$ de los elementos que se han comparado alguna vez y se les asignó un valor mayor a $z$; y
• $c$ es el cardinal del conjunto $C$ de los elementos que se han comparado alguna vez y se les asignó un valor menor a $z$.

El algoritmo no conoce la mediana hasta el final (es decir, no sabe qué tipo de comparación está realizando). Cuando se comparen dos elementos de $A$, el adversario les dará a uno un valor mayor y a otro un valor menor que $z$. Cuando se compare un elemento de $A$ con uno de $B$, le asignará al de $A$ un valor menor a $z$. Cuando se compare un elemento de $A$ con uno de $C$, le asignará al de $A$ un valor mayor a $z$. Note que en estos tres casos, la comparación resultará no ser crucial. Cuando se comparen elementos de $B$ ó $C$, responderá según los valores que ya ha asignado (estas comparaciones podrían ser cruciales).

Con estas decisiones del adversario, la siguiente tabla muestra cómo progresa el estado $(a,b,c)$ según los elementos que se comparan:

$$\begin{array}{|c|c|c|c|} \hline & A & B & C \\ \hline A & (a-2,b+1,c+1) & (a-1,b,c+1) & (a-1,b+1,c) \\ \hline B & & (a,b,c) & (a,b,c) \\ \hline C & & & (a,b,c) \\ \hline \end{array}$$

Si llegamos a $b=\frac{n-1}{2}$, el adversario asignará a $C$ todos los elementos aún no comparados (es decir, les dará valores menores a $z$), salvo uno que se reservará para asignarle el valor $z$. Similarmente, si llegamos a $c=\frac{n-1}{2}$, el adversario asignará a $B$ todos los elementos aún no comparados menos uno. Con ello, $z$ resultará ser la mediana, como era el plan del adversario.

De la tabla se deduce que, como partimos de $(n,0,0)$ y continuamos hasta que $b$ ó $c$ son $\frac{n-1}{2}$, necesitamos al menos ese número de comparaciones de la primera fila de la tabla, todas las cuales son no cruciales. Se deduce entonces la cota inferior de $\frac{3(n-1)}{2}$ comparaciones para encontrar la mediana.

Se puede usar el mismo razonamiento para demostrar que encontrar el $k$-ésimo elemento de un conjunto requiere $n+\min(k,n-k)-2$ comparaciones, si bien esta cota no es ajustada.