Complejidad temporal de escribir un número como potencia de 2

Question

Me pregunto por la complejidad temporal de escribir un número como potencia de 2. Por ejemplo escribiendo $n=218$ como $2 + 2^3 + 2^4 + 2^6 + 2^7$ . Me parece que sí $\lceil log_2^n \rceil $ divisiones. Cada división cuesta $O(n^2)$ por lo que un límite superior es $O(n^2 \cdot log_2^n)$ . Sin embargo, esto me parece un límite superior muy débil, ya que el número con el que empezamos se reduce con cada división. Entonces, ¿cuál sería un mejor límite superior en la complejidad de tiempo de escribir un número entero $n$ como potencia de 2?

Answer 1

Suponemos que el número inicial tiene $d$ dígitos. La prueba de paridad toma un tiempo constante, mientras que las divisiones por $2$ puede hacerse en tiempo lineal $O(d)$ (dividir los dígitos por la mitad de izquierda a derecha y llevarlos a la derecha cuando impar). Como esto se repite $d$ veces, la complejidad global es $O(d^2)=O(\log^2n)$ .

[La longitud del número disminuye efectivamente en cada división, pero el efecto neto es sólo reducir a la mitad el número de operaciones, por lo que la complejidad se mantiene $O(d^2)$ .]

Answer 2

La complejidad de la aritmética de precisión múltiple, Richard Brent, página 14 muestra que la complejidad de convertir una base arbitraria $\beta$ a base 2 tiene complejidad $O(M(w) \log(w))$ , donde $w$ es la cantidad de dígitos necesarios para representar el número en base 2 y $M(w)$ es la complejidad temporal de multiplicar dos $w$ -bit enteros. En su caso $w = \lceil {\log_2 (n+1)} \rceil$ .

Si utilizamos el algoritmo de Schönhage-Strasse para la multiplicación obtenemos una complejidad total de:

$O(w \cdot(\log w)^2 \cdot\log \log w) = O(\log n \cdot (\log \log n)^2 \cdot\log \log \log n)$

Answer 3

Usando el algoritmo que usted sugiere podemos sumar el trabajo de todas las divisiones $\sum_{i = 0}^{\log_2(n)} \left(\frac{n}{2^i} \right)^2 = \sum_{i = 0}^{\log_2(n)} \frac{n^2}{4^{i}} = n^2 \sum_{i = 0}^{\log_2(n)} \left(\frac{1}{4}\right)^i = 4n^2 \frac{1 - 4^{-\log_2(n) - 1}}{3} = \frac{4n^2}{3} (1 - 0.25n^{-2}) = \Theta(n^2)$