Máximo de un arreglo

Consideremos el problema de buscar el máximo elemento en un arreglo $A[1,n]$ mediante comparaciones. Es decir, los elementos de $A$ son cajas negras donde la única operación que podemos hacer sobre ellos es compararlos. Para simplificar, supondremos que todos los elementos son distintos.

El algoritmo más simple es tomar $A[1]$ como máximo provisional, y luego comparar ese máximo con $A[2]$, $A[3]$, y así hasta $A[n]$, manteniendo siempre el máximo visto hasta ahora. Para un arreglo $A[1,n]$ requerimos entonces $n-1$ comparaciones.

Un algoritmo alternativo es el llamado "torneo de tenis": Comparamos $A[1]$ con $A[2]$, comparamos $A[3]$ con $A[4]$, $A[5]$ con $A[6]$, etc. Luego, en un nuevo arreglo de los $n/2$ ganadores (mayores que el otro) en las comparaciones, volvemos a hacer una ronda de comparar a cada impar con el par que le sigue, y continuamos hasta tener un único ganador. Las comparaciones forman un árbol binario donde las $n$ hojas son los elementos de $A$ y cada nodo interno es una comparación, por lo que se hacen también $n-1$ comparaciones.

Cota inferior

Veamos que efectivamente se necesitan $n-1$ comparaciones para encontrar el máximo. Usaremos el modelo siguiente. El conocimiento que algoritmo tiene sobre el input es un grafo de $n$ nodos $(1),\ldots,(n)$. Cada vez que el algoritmo compara dos elementos $A[i]$ y $A[j]$, agregamos una arista entre los nodos $(i)$ y $(j)$. El estado inicial es el grafo sin aristas.

Para establecer los estados finales, notemos que un grafo no conexo no puede ser final. Si no existe un camino entre $(i)$ y $(j)$, el algoritmo no puede saber cuál es mayor a partir de las comparaciones realizadas, incluso aplicando transitividad. El adversario puede decidir que todos los elementos de la componente conexa de $(i)$ son mayores o menores que todos los de la de $(j)$ sin violar ninguna de las respuestas que ya ha dado. Por lo tanto, si el algoritmo declara que el máximo es un determinado $A[i]$, existe un input para el cual el resultado es incorrecto si existe un $A[j]$ en otra componente conexa.

Por lo tanto, los estados finales deben ser grafos conexos. Como se necesitan al menos $n-1$ aristas para conectar un grafo de $n$ nodos, $n-1$ es una cota inferior al problema de encontrar el máximo de un arreglo. Como tenemos algoritmos que usan $n-1$ comparaciones, sabemos que son óptimos y que esta cota inferior es ajustada, a pesar de que sólo consideramos una condición bastante débil acerca de lo que debe conocer el algoritmo sobre el input: nos bastó que existiera un camino de comparaciones que conectara a cualquier par de elementos.

Otro modelo

Consideremos ahora un modelo completamente distinto. El conocimiento del algoritmo sobre el input se describirá con tres variables $(a,b,c)$:

• $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 han ganado (han resultado mayores) en todas sus comparaciones; y
• $c$ es el cardinal del conjunto $C$ de los elementos que han perdido (han resultado menores) en alguna comparación.

El estado inicial es $(n,0,0)$, y está claro que el estado final debe ser $(0,1,n-1)$, pues si $a>0$ hay un elemento sin comparar (y el adversario se encargará de que ése sea el máximo) y si $b>1$ hay dos elementos que han ganado todas sus comparaciones (y si el algoritmo declara ganador a uno de ellos el adversario puede decidir que es menor que el otro). Cada comparación mueve elementos dentro de la tupla $(a,b,c)$. Según de qué conjunto vengan los elementos que el algoritmo compara, la siguiente tabla indica los posibles nuevos estados a partir de un estado $(a,b,c)$:

$$\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) \\ & & & (a-1,b,c+1) \\ \hline B & & (a,b-1,c+1) & (a,b,c) \\ & & & (a,b-1,c+1) \\ \hline C & & & (a,b,c) \\ \hline \end{array}$$

Por ejemplo, el resultado de la celda $\langle A,A\rangle$ es el de comparar dos elementos que nunca habían sido comparados: ambos salen del conjunto $A$, uno pasa a haber ganado todas sus comparaciones ($B$) y otro a haber perdido alguna comparación ($C$), por lo tanto el nuevo estado es $(a-2,b+1,c+1)$. El caso $\langle A,B \rangle$ nos lleva a $(a-1,b,c+1)$ independientemente de que el ganador sea el elemento de $A$ o el de $B$ (si el de $A$ gana, pasa a estar en $B$ pero el que estaba en $B$ pasa a $C$). El caso $\langle A,C \rangle$ puede llevar a dos estados distintos dependiendo de quién gane la comparación. Como el elemento de $A$ nunca se había comparado, el adversario puede decidir cuál de los dos resultados es el que ocurrirá. En particular, el adversario podría elegir la estrategia de "los que han perdido siguen perdiendo", con lo cual elige $(a-1,b+1,c)$ en este caso, y elige $(a,b,c)$ para el caso $\langle B,C \rangle$ (pues el adversario puede hacer que un elemento de $B$ sea tan grande como desee).

En cualquier caso, podemos observar que $c$ crece a lo sumo de a uno, y como debe pasar de $0$ a $n-1$, se necesitan al menos $n-1$ comparaciones para llegar al estado final.

Esta técnica nos sugiere algoritmos óptimos más claramente que la del grafo. Primero es necesario comparar $\langle A,A \rangle$. Luego, manteniendo $b=1$, podemos seguir siempre comparando $\langle A,B \rangle$ (es decir, el único que ha ganado siempre contra uno que no se ha comparado), para mover los otros $n-2$ elementos de $A$ a $C$. Puede verse que esta es la estrategia de nuestro primer algoritmo. Alternativamente, podemos utilizar $\langle A,A \rangle$ $n/2$ veces, hasta vaciar $A$ y tener $b=n/2$, y luego comparar $\langle B,B \rangle$ $n/2-1$ veces hasta dejar un solo elemento en $B$ y el resto en $C$. Note que en la segunda fase se comparan siempre ganadores con ganadores, lo que es compatible con nuestro algoritmo del torneo de tenis. Está claro que ningún algoritmo debería volver a comparar elementos de $C$, pues el adversario podría hacer que no avance hacia el estado final.