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$.

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. 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$.