Algoritmos y Estructuras de Datos - VJ1215

Ayuda del ejercicio 9 del tema 1

Para ir desde n hasta 1 de uno en uno hacen falta O(n) etapas. Por ello, un algoritmo recursivo basado en lo que ilustra el siguiente ejemplo tendría coste temporal O(n). Si no ves correctamente estas fórmulas, prueba con Firefox, que entiende MathML.

x^{100} = x^{99} \cdot x

x^{99} = x^{98} \cdot x

x^{98} = x^{97} \cdot x

x^{97} = x^{96} \cdot x

x^{96} = x^{95} \cdot x

\dots

x^{1} = x

x^{0} = 1

Pero para ir desde n hasta 1 dividiendo por 2 hacen falta O(log n) etapas. Piensa cómo aprovechar eso en este problema, utilizando propiedades matemáticas de la exponenciación.

Más ayuda (mírala después de pensarlo)

El siguiente ejemplo ilustra cómo podemos ir dividiendo la talla por 2 en este problema:

x^{100} = x^{50} \cdot x^{50}

x^{50} = x^{25} \cdot x^{25}

x^{25} = x^{12} \cdot x^{12} \cdot x

\dots