Incrementar un Número Binario

Seguiremos con un problema también de juguete, aunque algo más complicado y con una aplicación que veremos después. Supongamos que debemos incrementar un número binario de $k$ dígitos, desde $0$ hasta $2^k-1$. Llamemos $n=2^k$. Consideremos que el costo de incrementar un número es la cantidad de bits que debemos invertir. Como se invierten todos los 1s hasta el primer 0 de derecha a izquierda, el costo de incrementar varía entre 1 y $k$ según el número que incrementemos. Subrayamos a continuación los bits invertidos para $k=4$.

$$\begin{array}{l} 000\underline{0}~~~010\underline{0}~~~100\underline{0}~~~110\underline{0}\\ 00\underline{01}~~~01\underline{01}~~~10\underline{01}~~~11\underline{01}\\ 001\underline{0}~~~011\underline{0}~~~101\underline{0}~~~111\underline{0}\\ 0\underline{011}~~~\underline{0111}~~~1\underline{011}~~~1111\\ \end{array}$$

El peor caso es, como dijimos, tener que invertir $k$ bits (al pasar de de $2^{k-1}-1$ a $2^{k-1}$), por lo cual la secuencia de las $n$ inversiones cuesta $kn = O(n\log n)$ operaciones. Esto es cierto, pero no ajustado. Veremos que en realidad, se realizan en total menos de $2n = O(n)$ inversiones de bits, es decir, el costo amortizado de incrementar cada número es a lo más $2$.

--> imagen de ambas estrategias

Análisis global

La primera forma de verificar esto es mirar los costos de una forma diferente, que permita sumarlos con más facilidad. Miremos los bits subrayados por columnas y no por filas. Así se verá que el último bit del número cambia siempre, el penúltimo cambia una vez cada $2$, el antepenúltimo cambia una vez cada $4$, y así. Sumando los bits subrayados por columnas tenemos $n + \frac{n}{2} + \frac{n}{4} + \ldots < 2n.$

Contabilidad de costos

La segunda forma es notar que cada operación realiza exactamente una inversión de la forma $0 \rightarrow 1$, y cero o más inversiones $1 \rightarrow 0$. Como comenzamos con una secuencia de 0s, todo 1 fue un 0 alguna vez. Podemos entonces cobrarle 2 operaciones a las inversiones $0 \rightarrow 1$, y cobrarle cero a las inversiones $1 \rightarrow 0$. De este modo, cobramos por adelantado en las inversiones $0 \rightarrow 1$ la posible futura inversión $1 \rightarrow 0$ de ese bit. Obtenemos entonces una cota superior fácil de sumar: $n$ incrementos cuestan $2n$ inversiones a lo sumo.

Función potencial

Nuestra función potencial podría ser el número de 1s en la secuencia de bits actual. Tenemos entonces $\phi_n \ge 0$ y $\phi_0 = 0$. Consideremos lo que ocurre al incrementar una secuencia que termina con un último 0 y después $\ell$ 1s.

--> imagen

Se invierten el 0 y todos los 1s, por lo que el costo real es $c_i = \ell+1$. Por otro lado, se pierden $\ell$ 1s y se gana uno (al convertir el 0 a 1), por lo cual $\Delta\phi_i = -\ell+1$. Esto nos da $\hat{c_i} = c_i + \Delta\phi_i = 2$, y hemos obtenido nuevamente nuestro costo amortizado.

Nuevamente, los análisis son válidos si partimos de $k$ 0s y realizamos $2^k$ incrementos o menos, pero no si partimos de otra secuencia de bits. Por ejemplo, si partimos de $2^{k-1}-1$ y realizamos $n=1$ operaciones, entonces el costo, real o amortizado, por operación es $k$, no $2$.