Máximo y segundo máximo de un arreglo

Supongamos que deseamos encontrar el máximo y el segundo máximo elemento de $A[1,n]$. Una solución simple es encontrar el máximo y luego volver a encontrar el máximo entre los elementos restantes. Esto nuevamente cuesta $2n-3$ comparaciones. ¿Será óptimo? ¿Será que este problema es intrínsecamente más difícil que el de encontrar el máximo y el mínimo?

La analogía con el torneo de tenis nos sugiere una forma mucho mejor de resolver este problema. En un torneo de tenis, el segundo mejor debe haber jugado contra el primero, y sólo contra éste puede haber perdido. Como el primero realizó (y ganó) $\lceil \log_2 n \rceil$ partidas, hay sólo $\lceil \log_2 n \rceil$ candidatos para el segundo puesto. Una vez realizado el torneo de tenis para encontrar el máximo, podemos encontrar el segundo máximo entre los que perdieron contra el máximo usando $\lceil \log_2 n \rceil-1$ comparaciones. El costo total es entonces $n+\lceil \log_2 n \rceil-2$, lo que muestra que este problema es en realidad más fácil que el de encontrar el máximo y el mínimo, pues aquél requiere de $\lceil \frac{3}{2}n\rceil-2$ comparaciones.

La pregunta natural es si nuestro algoritmo es óptimo, o el problema se puede resolver aún mejor.

Cota inferior incorrecta

Intentemos reusar el modelo de la tabla, con los siguientes conjuntos:

• $a$ es el cardinal del conjunto $A$ de los elementos que nunca han sido comparados;
• $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 han perdido (han resultado menores) exactamente una vez; y
• $d$ es el cardinal del conjunto $D$ de los elementos que han perdido más de una vez.

El estado inicial es $(n,0,0,0)$ y el final debe ser $(0,1,1,n-2)$. La tabla es como sigue:

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

Tal como en el caso del mínimo y máximo, obtenemos una cota inferior de $\lceil \frac{3}{2}n \rceil-2$. ¡Pero esto no puede ser, ya tenemos una cota superior menor! ¿Qué ha ocurrido?

Lo que ha ocurrido es que nos hemos equivocado al suponer que es necesario llegar al estado $(0,1,1,n-2)$ para poder responder. En el torneo de tenis, casi la mitad de los jugadores juega un solo partido y queda descartada como primero o segundo, sin necesidad de haber perdido dos veces. La razón es la transitividad: si se pierde contra alguien que no es el mejor, no se puede ser el segundo mejor. Es decir, el algoritmo infiere cosas por transitividad, sin hacer comparaciones directas. Incluimos este ejemplo para mostrar que debe tenerse cuidado al aplicar esta técnica, asegurándose de que realmente es necesario llegar al estado final para poder responder correctamente.

Cota inferior correcta

Digamos que en un algoritmo que encuentra el máximo hay $m$ elementos que se comparan directamente (y pierden) contra quien finalmente resulta ser el máximo. El segundo máximo es entonces el mayor de estos $m$ candidatos (el segundo máximo debe haberse comparado contra el máximo, pues si no, ganó todas sus comparaciones y el adversario podría hacerlo arbitrariamente grande, incluso mayor que quien el algoritmo entrega como el máximo).

Consideremos de nuevo el modelo del grafo que se conecta. Si quitamos al nodo del máximo y a las $m$ aristas que lo conectan con los candidatos a segundo máximo, el grafo debe aún resultar conexo para poder determinar el segundo máximo. De no ser así, existen dos componentes conexas que se unían sólo pasando por el máximo, y el paso por el máximo no sirve para determinar en cuál de las dos componentes está el segundo máximo.

Por lo tanto el grafo debe tener al menos $n+m-2$ aristas, y se necesitan al menos $n+m-2$ comparaciones para encontrar el máximo y el segundo máximo ($n-1$ para el primero y $m-1$ para el segundo). Mostraremos que un adversario puede conseguir que $m=\lceil \log_2 n \rceil$.

Consideremos el siguiente modelo para la cota inferior. Se asocia un peso $w(i)$ a cada celda $A[i]$, inicialmente $w(i)=1$. Cuando un elemento $A[i]$ pierda una comparación, su $w(i)$ pasará a ser cero. Por lo tanto, para entregar el máximo correctamente, se requiere que haya un único $w(k)>0$ (donde $A[k]$ será entonces el máximo).

Ahora diseñemos un adversario adecuado. Cuando el algoritmo compara $A[i]$ con $A[j]$, hay tres casos:

1. Si $w(i) > w(j)$, el adversario responde que $A[i] > A[j]$. Esto es consistente porque $A[i]$ no ha perdido ninguna comparación. Asimismo, el adversario actualiza $w(i) \gets w(i) + w(j)$ y $w(j) \gets 0$. Este caso incluye el $w(i) < w(j)$, mediante intercambiar $i$ y $j$.
2. Si $w(i) = w(j) > 0$, el adversario se comporta como en el caso anterior, eligiendo arbitrariamente quién es $i$ y quién $j$.
3. En otro caso, el adversario da cualquier respuesta que sea consistente con las anteriores (es decir, si de las comparaciones pasadas se puede deducir el resultado de esta comparación, ese resultado debe mantenerse). En este caso, no se actualizan las $w$.

Puede verse que este adversario agrega un par de invariantes más al modelo: (1) todas las $w$ suman siempre $n$, y (2) cuando un $w(i)$ crece, a lo sumo se duplica. Eso implica que, para cuando el algoritmo puede responder correctamente que $A[k]$ es el máximo, vale que $w(k)=n$, y como llegamos de $w(k)=1$ a $w(k)=n$ a lo sumo duplicándolo en cada comparación, el elemento $A[k]$ debe haberse comparado directamente al menos $\lceil \log_2 n\rceil$ veces.

Note que la cota inferior de $n-1$ comparaciones para el máximo no requiere que el adversario responda de alguna manera especial en las comparaciones, por lo que podemos usar en particular este adversario para garantizar que, además de las $n-1$ comparaciones para encontrar el máximo, se requerirán otras $\lceil \log_2 n \rceil-1$ para el segundo máximo.

Finalmente, note que ningún algoritmo puede decir cuál es el segundo máximo si no sabe cuál es el máximo, pues eso significa que el segundo máximo propuesto no ha perdido ninguna comparación, y el adversario podría hacer que el segundo máximo propuesto fuera tan grande como quisiera. Por lo tanto, encontrar el segundo máximo es equivalente en dificultad a encontrar el primer y segundo máximo.