Técnicas

Comencemos con un problema de juguete para ejemplificar las técnicas a medida que las describimos. Supongamos que tenemos una pila donde permitimos las operaciones $push(x)$ (que apila $x$) y $multipop(k)$ (que desapila $k$ elementos con algún propósito, por ejemplo entregar su suma). La operación $push(x)$ cuesta $\Theta(1)$ y la operación $multipop(k)$ cuesta $\Theta(k)$ (supondremos que cuando se ejecuta es porque hay al menos $k$ elementos en la pila). La pregunta es ¿cuánto puede costar una secuencia de $n$ operaciones en una pila vacía?

--> imagen del funcionamiento de la estructura

Un análisis de peor caso nos muestra que, luego de haber realizado $\Theta(n)$ $push$'s, un $multipop$ nos puede costar $\Theta(n)$. Por lo tanto, una secuencia de $n$ operaciones partiendo de una pila vacía puede costar $O(n^2)$. Si bien esto es formalmente cierto, la cota está lejos de ser ajustada. Usaremos tres tipos de argumentos para mostrar que en realidad $n$ operaciones sólo pueden costar $O(n)$, es decir, el costo amortizado por operación es $O(1)$ (si bien es verdad que algún $multipop$ puede costar $\Theta(n)$).

Análisis global

La primera forma de verificar esto es notar que, en $n$ operaciones, sólo se pueden haber apilado $n$ elementos mediante $push$'s. Por ello, si bien algún $multipop$ puede costar casi $n$, la suma de todos los $multipop$'s sólo puede costar $n$, pues todo elemento desapilado se debe haber apilado alguna vez. Es decir, con $n$ operaciones a lo sumo podemos haber apilado $n$ elementos y luego haberlos desapilado. Si tomamos el costo de $push$ como $1$ y de $multipop(k)$ como $k$, el costo total de las $n$ operaciones es a lo más $2n = O(n)$.

Esta técnica se llama análisis global: observamos los costos de toda la secuencia no paso a paso sino globalmente, para deducir alguna propiedad que permita acotar el costo total. Ésta es la más sencilla de las técnicas, aunque no siempre es fácil encontrar una visión global que haga obvio el costo total.

Contabilidad de costos

La segunda forma es notar que cada elemento que se saca con $multipop$ debe haber entrado en la pila con un $push$ alguna vez. Podemos entonces cobrarle 2 operaciones al $push$, y cobrarle cero al $multipop$. Visto de otro modo, le estamos cobrando por adelantado al elemento $x$ de $push(x)$ el costo que producirá cuando más adelante participe de un $multipop(k)$. Queda entonces claro que una secuencia de $n$ operaciones no puede costar más que $2n$, pues no puede haber más de $n$ operaciones de $push$.

Esta técnica se llama contabilidad de costos: repartimos el costo real de alguna forma, entre operaciones, objetos, etc. para que resulte más fácil de sumar. Podemos, en particular, cobrar costos futuros por adelantado. La dificultad está en encontrar, precisamente, una forma de distribuir los costos que haga evidente el costo total.

Función potencial

Esta técnica consiste en definir una función $\phi$ que depende del objeto que vamos modificando a lo largo de las operaciones. Esta función representa un "ahorro" que vamos haciendo en las operaciones más baratas para poder usarlo en pagar las operaciones más caras a futuro.

Pensemos en un contratista de una obra. Algunos meses tiene más gastos y otros menos. Para tener una interfaz sencilla con su cliente, todos los meses $i$ le cobra lo mismo, $\hat{c_i} = c$. Sin embargo, su costo real, $c_i$, es variable. En los meses en que $c_i \le \hat{c_i}$, ahorrará el sobrante $\hat{c_i}-c_i$ en una bolsa llamada $\phi$. En los meses en que $c_i > \hat{c_i}$, pagará la diferencia $c_i-\hat{c_i}$ con el ahorro que tiene en la bolsa $\phi$. Llamamos $\phi_0$ al ahorro inicial con que se comienza la obra y $\phi_i$ a lo que tiene ahorrado después del mes $i$. Entonces, se cumple la recurrencia $\phi_i = \phi_{i-1} + \hat{c_i} - c_i$. Como la obra se puede detener en cualquier momento, para asegurarse de no perder dinero el contratista necesita que en todo mes $i$ valga $\phi_i \ge \phi_0$. Desde el punto de vista del cliente, el costo de la obra es constante por mes, $\hat{c_i}$. Esto corresponde al costo amortizado de la operación del contratista, que usa el ahorro para esconder una estructura de costos más complicada.

Formalmente, tenemos entonces una secuencia de costos reales $c_i$ y una función potencial con valor $\phi_i$ luego de la operación $i$. Si llamamos $\Delta \phi_i = \phi_i - \phi_{i-1}$, definimos la secuencia de costos amortizados $\hat{c_i}$ como

$$\hat{c_i} ~=~~ c_i + \Delta\phi_i.$$

Con esta definición tenemos

$$\begin{array}{c c c} \sum_{i=1}^n \hat{c_i} & = & \sum_{i=1}^n (c_i + \Delta\phi_i), \\ \sum_{i=1}^n \hat{c_i} & = & \left(\sum_{i=1}^n c_i\right) + \phi_n - \phi_0, \\ \sum_{i=1}^n \hat{c_i} & \ge & \sum_{i=1}^n c_i, \\ \end{array}$$

donde lo último se cumple si nos aseguramos de que $\phi_n \ge \phi_0$ para toda secuencia de operaciones. Entonces nuestra secuencia de costos amortizados es una cota superior a la secuencia de costos reales.

La dificultad está siempre en definir $\phi$ adecuadamente para que se mantenga $\phi_n \ge \phi_0$ y sobre todo que los $\hat{c_i}$ resultantes sean fáciles de sumar (constantes, idealmente). Para ello, las operaciones que cuestan mucho deben disminuir el potencial en la misma medida.

En nuestro ejemplo, el potencial podría ser el alto de la pila. Tenemos entonces $\phi_n \ge 0$ y $\phi_0 = 0$. Consideremos lo que ocurre al ejecutar $push(x)$. El costo real es $c_i = 1$. Por otro lado, la pila se hace una unidad más alta, por lo que $\Delta\phi_i = 1$. Esto nos da $\hat{c_i} = c_i + \Delta\phi_i = 2$. Por otro lado, al realizar un $multipop(k)$ tenemos un costo real de $c_i = k$, pero como el alto de la pila decrece en $k$, tenemos $\Delta\phi_i = -k$, con lo cual el costo amortizado es $\hat{c_i} = c_i + \Delta\phi_i = 0$. Nuevamente, hemos obtenido nuestro costo amortizado de a lo más 2 unidades por operación.

Note que los análisis son válidos si partimos de la pila vacía, pero no si partimos operando con una pila que ya tiene $k$ elementos. En ese caso, una sola operación $multipop(k)$ cuesta $O(k)$ y no $O(1)$. Note que aquí hemos violado algún supuesto hecho en cada una de las tres formas de analizar este problema.