Este es el manual del cuarto entrenamiento intermedio de la OIE: Análisis amortizado.
A medida que avances con la algoritmia, te será fundamental saber analizar la complejidad de tus programas lo más rigurosamente posible. Normalmente, conocemos cuánto tarda un algoritmo (de forma proporcional al tamaño de la entrada) en el peor de los casos, pero no siempre se ejecuta nuestro programa en el peor de los casos y, si llamamos a una función varias veces sobre una misma estructura de datos, a veces podemos calcular cuántos de estos casos serán el peor caso y ver si la complejidad del resto de casos compensa las operaciones extra realizadas en los casos complicados. De esto trata la técnica de análisis amortizado, que consiste en analizar el análisis de un algoritmo durante varias operaciones para comprobar si la complejidad del peor caso realmente es la complejidad media de toda serie arbitraria de operaciones. Aprenderemos esta técnica a través de varios ejemplos, en los que aplicaremos el método agregado para calcular la complejidad de nuestro algoritmo. Este nos ayudará a ver si nuestras estimaciones sobre la complejidad de un algoritmo son demasiado pesimistas.
Ejemplo: array dinámico
Para presentar la técnica del análisis amortizado un buen ejercicio es implementar una estructura de datos similar al vector de C++ pero utilizando únicamente arrays. Con similar a un vector me refiero a que tenga las siguientes características:
- Añadir $m$ elementos partiendo de una lista vacía (pudiendo intercalar en el medio las siguientes dos operaciones también) debe tener una complejidad de $O(m)$.
- Mirar el valor de cualquier posición de la lista en $O(1)$.
- Saber el tamaño de la lista en $O(1)$.
Antes de seguir leyendo, para a pensar en si se te ocurre cómo harías esto. Trata por ejemplo de crear una struct con estas características.
Una forma de hacer esto es inicialmente crear un array de tamaño 1 llamado $A$ y guardar en un entero longitud el tamaño de $A$ (inicialmente 0). Cuando el usuario quiera añadir un valor al final de la lista, lo añadiremos a la posición longitud de $A$ e incrementaremos el valor de longitud. Siempre que longitud sea una potencia de 2, crearemos un array del doble de tamaño y migraremos los elementos de $A$ al nuevo array, haciendo que $A$ pase a tener el doble de tamaño. Además, mirar el valor de una posición de la lista será muy sencillo, ya que simplemente podemos mirar el valor de esa posición en $A$.
Las dos últimas de las tres características que buscábamos es fácil ver que se cumplen. Sin embargo, ¿por qué añadir m elementos tiene una complejidad de $O(m)$? Al fin y al cabo, si tenemos la mala suerte de que justo sea el momento en el que longitud sea una potencia de 2, tardaremos $O(longitud)$ en añadir un único elemento. Bueno, lo que pasa aquí es que, aunque longitud va creciendo con el tiempo, su ritmo de crecimiento es igual al ritmo de crecimiento de los espacios entre las operaciones caras y, por lo tanto, se compensa una cosa con otra. Demostremos esto de forma más rigurosa.
Analizaremos ahora el coste de insertar $m$ elementos. Pongamos que $m = 2^k + r$, con $k, r \in \mathbb{Z}^{\geq 0}$ y $0 \leq r < 2^k$. Tomaremos como una operación de tiempo constante el darle valor a una posición concreta de A, ya reservada pero vacía, y como una operación de tiempo negligible el reservar un array del doble de tamaño que la actual. El número total de operaciones es entonces:
$\sum_{i=1}^{2^k + r} 1 + \sum_{j = 2}^k (2^{j-1} - 1)$ (sumamos 1 por cada elemento añadido y $2^{j-1}$ cada vez que reservemos un array de tamaño $2^j$ por mover todos los elementos, restando 1 por el nuevo elemento, que ya hemos contado en el primer sumatorio)
$= \sum_{i=1}^{2^k + r} 1 + \sum_{j = 2}^k 2^{j-1} - \sum_{j = 2}^k 1$
$= \sum_{i=1}^{2^k + r} 1 + \sum_{j = 1}^{k-1} 2^j - \sum_{j = 2}^k 1$
$= 2^k + r + 2^k - 1 - 1 - (k-1)$
$= 2 \times 2^k - 1 + (r-k)$
$= 2 \times 2^k + 2r - k - r - 1$
$= 2(2^k + r) - k - r - 1$
$= 2m - k - r - 1$
$= O(m)$, tal y como esperábamos.
No en todos los problemas podremos usar esta técnica para ajustar la complejidad, pero es una herramienta útil para tener a mano. En casos como este, decimos que las inserciones a nuestra lista tienen complejidad $O(1)$ amortizada, ya que no en todas las inserciones se dará el caso.
Ejercicios de este entrenamiento:
- Implementa una struct que imite a un stack en los siguientes sentidos y demuestra utilizando la técnica de este manual que sus complejidades se ajustan a los requisitos:
- Añadir un elemento al stack en $O(1)$ amortizado
- Quitar el elemento de arriba del todo en $O(1)$ amortizado
- Leer el elemento de arriba del todo en $O(1)$
- Mirar el tamaño del stack en $O(1)$
2. (Más complicado) Extiende la idea de imitación de un vector de este manual para que quitar elementos tenga complejidad de $O(1)$ amortizada también. Pista: ten en cuenta que podemos encontrarnos con secuencias donde justo cuando la longitud es una potencia de 2, repetidamente añadamos y quitamos elementos alternando estas dos operaciones.
Añadir nuevo comentario