Mínimo y máximo de un arreglo

Consideremos ahora el problema de encontrar el mínimo y el máximo de un arreglo $A[1,n]$. Una forma de resolver este problema es encontrar el máximo de $A[1,n]$ usando $n-1$ comparaciones, y luego, excluyendo el máximo, encontrar el mínimo de los $n-1$ elementos restantes usando $n-2$ comparaciones. En total este algoritmo realiza $2n-3$ comparaciones.

Para ver si es óptimo, usaremos un modelo que extiende el que acabamos de usar, dividiendo el conjunto en cuatro:

• $a$ es el cardinal del conjunto $A$ de los elementos que nunca han sido comparados (nuevamente, no confundir con el arreglo $A$);
• $b$ es el cardinal del conjunto $B$ de los elementos que se han comparado alguna vez y han ganado (han resultado mayores) en todas sus comparaciones;
• $c$ es el cardinal del conjunto $C$ de los elementos que se han comparado alguna vez y han perdido (han resultado menores) en todas sus comparaciones; y
• $d$ es el cardinal del conjunto $D$ de los elementos que han ganado alguna vez y también han perdido alguna vez.

El estado inicial es ahora $(a,b,c,d) = (n,0,0,0)$, y el estado final es $(0,1,1,n-2)$. La tabla de resultados de comparaciones es ahora la siguiente:

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

Hemos tachado resultados que el adversario podría evitar siempre con la estrategia de "los ganadores siguen ganando y los perdedores siguen perdiendo", que siempre es consistente. Podríamos tachar otros resultados, pero no es necesario para establecer nuestra cota inferior. Observe que (1) $a$ decrece a lo sumo de a dos, (2) $d$ crece a lo sumo de a uno, y (3) $a$ nunca decrece al mismo tiempo que $d$ crece. Entonces, como $a$ debe pasar de $n$ a $0$ y $d$ debe pasar de $0$ a $n-2$, tenemos una cota inferior de $\lceil \frac{3}{2}n \rceil -2$ comparaciones para resolver este problema.

Esta vez nuestra cota inferior es distinta de la cota superior $2n-3$. Nos podemos preguntar si será una cota inferior ajustada. Tal vez el modelo es muy débil o el adversario no es muy inteligente o nuestra observación sobre cómo llegar del estado inicial al final no es suficiente para demostrar que realmente se necesitan $2n-3$ comparaciones.

Veremos que no es así, usando el modelo para encontrar un algoritmo óptimo. La tabla sugiere que la forma más rápida de llegar al estado final es usar celdas $\langle A,A \rangle$ $n/2$ veces hasta llegar al estado $(0,n/2,n/2,0)$. Luego podemos usar $\langle B,B \rangle$ $n/2-1$ veces para llegar a $(0,1,n/2,n/2-1)$ y finalmente usar $\langle C,C \rangle$ $n/2-1$ veces para llegar al estado final, $(0,1,1,n-2)$. Esto equivale a realizar un primer nivel de torneo de tenis, comparando cada celda impar con la siguiente celda par, obteniendo $n/2$ ganadores y $n/2$ perdedores. Luego, buscamos (con cualquiera de los algoritmos vistos) el máximo entre los $n/2$ ganadores y el mínimo entre los $n/2$ perdedores. El costo total es $\lceil \frac{3}{2}n\rceil -2$ (note que se necesitan dos comparaciones más si $n$ es impar).

Con esto tenemos que la cota de $\lceil \frac{3}{2}n\rceil-2$ comparaciones es ajustada, que nuestro algoritmo inicial no era óptimo, y que usamos el modelo de la cota inferior para ayudarnos a encontrar un algoritmo óptimo en términos del número de comparaciones.