Considere la siguiente subrutina, ¿cuál es el tiempo de ejecución?

Supongamos que A(.) es una subrutina que toma como entrada un número en binario, y toma el tiempo O($n^2$), donde n es la longitud (en bits) del número.

(a) Considere la siguiente pieza de código, que comienza con un número x de n bits.

mientras que x > 1:

llamar A(x)

x = x/2

Suponga que la división por dos toma O(n) tiempo en un número de n bits.

En la primera iteración del ciclo interno, x tiene una longitud de n bits. ¿Cuál es la longitud de x durante la segunda iteración? ¿La tercera iteración?

¿Cuántas veces se ejecuta el ciclo interno? Deje su respuesta en forma de O grande.

¿Cuál es el tiempo total de ejecución (en términos de n)? Nuevamente, use O grande.

¿Es este un algoritmo de tiempo polinomial?

(b) Ahora responda las mismas preguntas para este fragmento de código alternativo.

mientras que x > 1:

llamar A(x)

x = x - 1

Suponga que la operación de resta toma O(n) tiempo en un número de n bits.

SOLUCIÓN

(a) En cada iteración del ciclo interno, x se reduce a la mitad y, por lo tanto, se reduce en un bit. Por lo tanto, hay como máximo n iteraciones. El tiempo total de ejecución es O($n^2 + (n - 1)^2 + ... + 1^2$) = O($n^3$), polinomio.

(b) En cada iteración del ciclo interno, x disminuye solo en 1. Por lo tanto, su longitud permanece igual durante aproximadamente$2^{n-1}$iteraciones, entonces para$2^{n-2}$iteraciones, etc. El tiempo total de ejecución es O($n^22^n$), exponencial.

en parte, creo que entiendo, acabo de tomar un ejemplo 8 que es 1000 en binario y cada vez que se reduce a la mitad se reduce en un bit de 8 (1000) a 4 (0100) a 2 (0010) a 1 (0001), yo puede ver concretamente el razonamiento detrás de la parte a. La parte B es un poco más confusa. No entiendo cómo se les ocurren las iteraciones y el tiempo de ejecución. ¿Puede alguien explicarme?