Capítulo 7. Divide y Conquista (Parte III)

Continuando con la serie de DyC, veremos en este capítulo un ejemplo de aplicación para resolver un algoritmo que calcule potencias de aⁿ cuando n es potencia de 2.

Antes de aventurarnos a escribir el pseudocódigo, analicemos un poco qué ocurre para a⁸

Podemos ver que los subproblemas 1 y 2 son idénticos, entonces carecería de sentido (en realidad se verá que se desperdiciarían recursos) hacer ambos. 

Lo más conveniente es tomar una sola mitad y luego multiplicar el resultado por sí mismo. Ahora sí podemos adentrarnos en el pseudocódigo para resolver el problema

Para el análisis de complejidad temporal observamos que el tamaño de la entrada disminuye a la mitad cada vez lo cual nos estamos en presencia del Caso 2 para métodos recursivos.

Los valores de a, b y k son 1, 2 y 0 respectivamente. Finalmente vemos que el orden del método para calcular potencias de 2 es O(log n).

Si no hubiésemos simplificado una de las ramas, tendríamos 2 llamadas recursivas en lugar de una sola:

R1 <- CALCULAR_POTENCIA(a, n1)

R2 <- CALCULAR_POTENCIA(a, n1)

De esta forma, a = 2, lo que finalmente se traduce en O(n), es decir, una complejidad temporal mayor a la calculada anteriormente.