Potencia de base y exponente entero recursiva con propiedades - dambort/algos GitHub Wiki

Problema: Dado un numero base a y un exponente n, se desea elevar la base a la n-esima potencia.

Ejemplos:

  1. Si a = 2; n = 4;
  • Salida: 16
  1. Si a = 5; n = 5;
  • Salida: 3125

Idea del algoritmo:

Ademas del uso de recursion como herramienta, utilizaremos una propiedad de la potenciacion para mejorar la complejidad del algoritmo. Dicha propiedad consiste en que el producto de potencias de igual base puede ser expresado como la suma de los exponentes de esas potencias, de manera análoga se puede descomponer una potencia en un producto de potencias de igual base, siempre y cuando la suma de los exponentes sea igual al exponente inicial.

Código

Disponible en Enciclopedia Algoritmos C++

Ejemplo de uso

Disponible en ejemplo potencia entera recursiva con propiedades

Complejidad: O(√n)