Cota Inferior

Demostraremos que este algoritmo de ordenamiento es óptimo si se procede por comparaciones. Para ello, volveremos a utilizar la estrategia del adversario. Ya vimos en el capítulo anterior que un algoritmo de ordenamiento debe permitir determinar en cuál de todas las $N!$ permutaciones se ha presentado el input. Nuestro modelo será el conjunto de las permutaciones consistentes con los datos que ha leído el algoritmo hasta ahora. En el estado inicial, este conjunto tiene las $S = N!$ permutaciones posibles, y en los estados finales este conjunto debe tener un único elemento, $S = 1$.

El algoritmo va reduciendo el tamaño $S$ del conjunto de permutaciones factibles a medida que lee un bloque de datos del disco y los compara contra lo que tenga almacenado en memoria. Al leer $B$ valores, si es la primera vez que los ve, el algoritmo puede compararlos entre sí para determinar cuál de los $B!$ posibles ordenamientos entre ellos es el correcto. Asimismo, si guarda otros $M-B$ valores en memoria, puede determinar de cuál de las ${M \choose B}$ formas se insertan estos $B$ valores entre los que tiene en memoria. En total, el algoritmo determina la configuración correcta entre las ${M \choose B} B!$ que eran posibles antes de leer el bloque (esto es optimista: podría ser que un algoritmo no lograra aprender tanto, pero lo importante es que no puede aprender más que esto).

Cada una de las $S$ permutaciones del input que aún son posibles es compatible con sólo una de estas configuraciones entre las que la lectura del bloque ha permitido distinguir. El conjunto de permutaciones se puede particionar entonces en ${M \choose B} B!$ subconjuntos, uno compatible con cada configuración. El adversario puede elegir cuál de estos subconjuntos es el que resulta compatible con el bloque leído, y tomará el mayor. El mayor subconjunto tiene un tamaño mínimo garantizado de $\frac{S}{{M \choose B} B!}$. Es decir, por bien que lo haga el algoritmo, el adversario puede encargarse de que $S$ se reduzca sólo por un factor de ${M \choose B} B!$ por cada bloque que lee. Si el algoritmo lee $t$ bloques, entonces a lo sumo puede reducir el tamaño del conjunto inicial a

$$\frac{N!}{{M \choose B}^t(B!)^t}.$$

Si seguimos por este camino llegaremos a una cota inferior válida, pero no ajustada. La razón es que hemos sido demasiado optimistas. La cantidad de lecturas de bloques a lo largo del algoritmo debe ser $t \ge n$, pues debe leer todo el input. Y de ellas, sólo las primeras $n$ pueden leer bloques nunca vistos. Por lo tanto, no se puede aprender el orden interno de los elementos del bloque (lo que aporta la componente $B!$) todas las $t$ veces que se lee, sino a lo sumo $n$ veces. (Se pueden escribir bloques nuevos a lo largo del algoritmo, pero como estos bloques se han escrito, entonces estuvieron juntos antes en memoria, por lo tanto el algoritmo ya sabía cómo se ordenaban internamente antes de escribirlos.) En conclusión, si el algoritmo lee $t$ bloques, realmente sólo puede reducir el conjunto de inputs compatibles a

$$\frac{N!}{{M \choose B}^t(B!)^n}.$$

Si calculamos ahora cuánto tiene que ser $t$ para que este valor llegue a $1$, tendremos

$$t ~~\ge~~ \frac{\log N! - n\log B!}{\log {M \choose B}}.$$

Usando la aproximación de Stirling e ignorando términos de orden inferior, tenemos

$$t ~~\ge~~ \frac{N\log N - N\log B}{M\log M - B\log B - (M-B)\log(M-B)},$$ $$t ~~\ge~~ \frac{N\log n}{B\log m + (M-B)\log\frac{M}{M-B}},$$ $$t ~~\ge~~ n\log_m n.$$

Lo que hicimos en el último paso fue usar que $\log\frac{M}{M-B} = \log(1+\frac{B}{M-B}) = O(\frac{B}{M-B})$ (pues $\ln(1+x) \le x$), y por lo tanto $(M-B)\log\frac{M}{M-B} = O(B)$, que es de orden inferior al término $B\log m$ que lo acompañaba.

Tenemos entonces que todo algoritmo que ordene en memoria externa por comparaciones requiere $\Omega(n\log_m n)$ I/Os.