Profundizando en la redimensión

[Martín Buchwald]

Hola a todos, 

El lunes, al hablar de políticas de redimensión (más específicamente de duplicar la cantidad de elementos del arreglo dinámico de la pila), Emiliano planteó la pregunta "Entonces, en realidad, el apilar se comporta como O(log n)?". 

La respuesta rápida, y para no ahondar demasiado en el tema y perder la mitad de la clase en demostraciones, fue decir "No, la cantidad de redimensiones es O(log n)".

Este mail está dirigido a aquellos a quienes eso no les convenció, o que aunque les pareció correcto, no ven como esa salvedad hace que la primitiva se mantenga en orden constante, o simplemente sienten curiosidad de saber cómo se demuestra formalmente algo como eso. Si no es su caso, pueden omitir este mail.

Supongamos que la política de redimensiones es de duplicar el tamaño de la pila cuando esta está llena, y supongamos que el tamaño inicial es de 1 (sólo para simplificar cuentas). Eso quiere decir que las redimensiones se realizarán cuando la cantidad de elementos sea alguna potencia de 2 (desde 2^0). Supongamos también que la cantidad de elementos es n = 2^k, para algún entero k (es fácil ver que k = log_2 (n)). 

Ahora bien, en clase mencionamos que la cantidad de redimensiones es correctamente log_2(n), puesto que justamente vamos a redimensionar en cada potencia de 2. Por lo tanto, redimensionaremos k veces.

Uno podría apurarse a decir "pero entonces, si cada una de esas redimensiones tarda O(n), podríamos decir que en total tenemos O(n log n), y por lo tanto, en promedio cada operación es O(log n)". Esto es técnicamente correcto, puesto que la notación Big Oh es una cota superior, pero si analizamos un poco más, vamos a ver que podemos encontrar una mejor cota. 

Lo que tenemos que pensar es "¿Todas esas redimensiones toman O(n)?". La verdad es que no. Cada redimensión toma O(n'), donde n' es el tamaño al momento de redimensionar. Muchas veces no tenemos este tipo de contemplaciones al calcular el orden, porque si se hace de manera continua el resultado es el mismo, pero acá las redimensiones se van haciendo de forma cada vez más espaciada! Entonces, cada operación de redimensión toma O(2^r), con r = 0,1, ..., k, según cada caso. 

Si queremos ver cuánto nos toma esto en total, podemos verificar cuanto nos cuesta: 

costo total = Σ costos = Σ O(2^r), para r desde 0 hasta h.

Para resolver eso, podemos aplicar la resolución de la progresión geométrica (no importa si no la conocen, ya la usarán en proba y análisis III): 

costo total = O((2^k - 1) / (2 - 1)) = O(2^k - 1)

Pero dijimos que 2^k = n, entonces:

costo total = O(n -1) = O(n). 

Ese es el costo total, de haber hecho todas las redimensiones. Entonces, el costo total de haber apilado n elementos es: O(n) por apilarlos + O(n) por redimensionar = O(n) en total. Si el factor de redimensión hubiera sido 3 en vez de 2, el resultado habría sido el mismo. 

Por lo tanto, podemos ver que con esta política de redimensión, no se afecta el orden total de la primitiva (que aplicándola una sola vez, será O(1)), que era lo que estábamos buscando.

Saludos!

MB