Tiempo de ejecución (Big O) del conteo en binario

Question

¿Cuál es el tiempo total de funcionamiento del conteo de 1 a $n$ en binario si el tiempo necesario para sumar 1 al número actual $i$ es proporcional al número de bits de la expansión binaria de $i$ que debe cambiar al pasar de $i$ a $i+1$ ?

No sé cómo hacerlo. Si el número $n$ tiene $m$ bits, entonces podemos decir $n = 2^m - 1$ por lo que la cantidad de bits utilizados para representar el número es $m = \lceil log_2(n+1) \rceil$ . La mayor cantidad de bits que se voltean al incrementar un número es toda $m$ bits. Eso es todo lo que tengo. ¿A dónde voy desde aquí?

Answer 1

El caso en el que $n=2^a$ para algunos $a$ es un poco más fácil de analizar. Observemos la lista de números binarios para $a=3$ :

0001
0010
0011
0100
0101
0110
0111
1000

Nos interesa saber cuántas veces hay un trozo que cambia. El truco es contar no un número a la vez sino una posición de bit a la vez:

• El bit de los unos cambia para cada número, por lo que se invierte $n$ tiempos.
• El bit de dos cambia por cada segundo número, por lo que se invierte $n/2$ tiempos.
• El bit de los cuatros cambia una de cada cuatro veces, por lo que se invierte $n/4$ tiempos.

Y así sucesivamente el número total de vueltas es $$\sum_{i=0}^a \frac{n}{2^i} = n \sum_{i=0}^a 2^{-i} < 2n$$ donde la última desigualdad se debe a que $\sum_{i=0}^a 2^{-i}$ es un prefijo de la serie geométrica infinita con suma $2$ .

Ahora, ¿puede demostrar que también hay $\le 2n$ se voltea cuando $n$ no es un poder de $2$ ?

Answer 2

Dejemos que $T(n)$ sea el tiempo de ejecución del conteo de $1$ a $n$ . Para determinar $O(T(n))$ sólo tenemos que mirar los valores si $n$ tal que $n=2^m$ para algunos $m\in\mathbb{N}$ como para cualquier $n$ tenemos algunos $m$ tal que $2^m\leq m<2\times 2^m=2^{m+1}$ y $T(n)$ es creciente, por lo que podemos aprovechar el hecho de que $O(T(n))$ ignora la constante $2$ . Entonces, ¿qué es $T(2^m)$ ? Bueno, es precisamente $2^m$ más las longitudes combinadas de todas las secuencias de unos al final de los números en $[1,2^m-1]$ ya que para cada número en este rango el número de bits volteados es uno más que el número de unos consecutivos al final del número. Por ejemplo, $100\mapsto 101$ (0 unos al final, 1 vuelta), $100111\mapsto 101000$ (3 unos, 4 vueltas). Como cada secuencia posible de unos y ceros de longitud $m$ ocurre exactamente una vez en el rango $[1,2^m-1]$ podemos simplemente contar con ellos. Hay $2^{m-2}$ secuencias que terminan en $01$ , $2^{m-3}$ secuencias que terminan en $001$ el mismo número para los que terminan en $010$ y $011$ y así sucesivamente. Te dejo que descubras una fórmula para el número de secuencias que terminan en precisamente x unos (lo que significa que quiere contar el número de secuencias con un cero entonces $x$ de los mismos, excepto en el caso $2^m-1=11\cdots1$ ) y encontrar la suma ponderada para obtener el tiempo de ejecución.

Answer 3

He aquí una fórmula exacta:

Para cualquier número entero positivo $n,$ dejar $T(n)$ sea el número total de bits que se invierten al contar desde $1$ a $n.$ Entonces $$T(n)= 2n - \text{(the number of }1\text{'s in the binary representation of }n)-1.$$ Es fácil demostrarlo por inducción:

Base:

$T(1)= 0 = 2 \cdot 1 - 1- 1.$

Paso de inducción:

Para mayor comodidad, escriba $B(n)$ para el número de $1$ en la representación binaria de $n.$

Supongamos que $T(n)= 2n - B(n)-1.$ Tenemos que demostrar que $T(n+1)= 2n+2 - B(n+1)-1.$

Si la representación binaria de $n$ termina exactamente con $k \; 1$ entonces podemos escribir $n$ en binario como $a_1 \dots a_j 0 1 1 1 \dots 1$ (con $k \; 1$ al final). (Tenga en cuenta que $k$ puede ser $0,$ pero no pasa nada). Así que $n+1$ en binario es $a_1 \dots a_j 1 0 0 0 \dots 0$ (con $k \; 0$ al final). Si se observa el número de $1$ en cada uno de ellos, se puede ver que $$B(n+1)=B(n)-k+1$$ (porque hay $k \; 1$ 's en $n$ que se pierden al pasar a $n+1,$ pero hay una $0$ en $n$ que se convierte en un $1$ en $n+1$ ).

Tenemos que dar la vuelta $k+1$ bits para contar desde $n$ a $n+1,$ así que \begin{align}T(n+1)&=T(n)+k+1 \\\\&=(2n - B(n)-1)+k+1 \\\\&=2n - B(n+1) + 1 \\\\&=2n+2 - B(n+1)-1,\end{align} como se desea, completando la prueba por inducción.

Así que ahora sabemos que para cada entero positivo $n,$ $$T(n)= 2n - \text{(the number of }1\text{'s in the binary representation of }n)-1.$$

Desde $T(n) < 2n$ para todos los enteros positivos $n,$ tenemos $T(n)=O(n).$ Para ver que esta es la mejor estimación posible de ese tipo, observe que $B(n)$ es como máximo $\lfloor \log_2(n)\rfloor+1,$ el número total de bits en la representación binaria de $n.$ Así que \begin{align} T(n) &= 2n-B(n)-2 \\\\& \ge 2n-\lfloor \log_2(n)\rfloor-3. \end{align}

Por cierto, probablemente valga la pena mencionar que esto no es lo que se suele llamar tiempo de ejecución lineal, porque eso se refiere a un tiempo de ejecución que es $O(n)$ donde $n$ es el número de bits de la entrada. En este problema, $n$ es valor de la entrada, no su tamaño . Si medimos el tiempo de ejecución de la manera habitual, basándonos en el tamaño de la entrada, entonces contando desde $1$ a $n$ requiere un tiempo de ejecución exponencial (exponencial en el número de bits del número binario $n).$