Complejidad Temporal
Mejor: O(log n)
Prom: O(log n)
Peor: O(log n)
La Exponenciación Binaria calcula aⁿ en O(log n) dividiendo el exponente a la mitad en cada paso, en lugar de multiplicar a por sí mismo n veces.
Cómo funciona:
1. Caso base: a⁰ = 1
2. Calcular recursivamente half = binPow(base, floor(exp / 2))
3. Si exp es par, retornar half × half
4. Si exp es impar, retornar half × half × base
Por qué es rápida:
Cada llamada recursiva corta el exponente a la mitad, así que la profundidad de la recursión es proporcional a log₂ n en vez de n.
Complejidad Temporal:
Mejor: O(log n)
Promedio: O(log n)
Peor: O(log n)
Complejidad Espacial: O(log n) por la pila de llamadas recursivas
Aplicaciones:
- Exponenciación modular en criptografía
- Exponenciación rápida de matrices
- Programación competitiva y teoría de números
La idea clave es reutilizar potencias: una vez que conoces a^(n/2), puedes elevarlo al cuadrado y recuperar la mayor parte del trabajo inmediatamente.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Exponenciación Binaria?
- La Exponenciación Binaria calcula aⁿ en O(log n) dividiendo el exponente a la mitad en cada paso, en lugar de multiplicar a por sí mismo n veces.
- ¿Cuál es la complejidad de Exponenciación Binaria?
- Tiempo (promedio): O(log n) · Espacio: O(log n)
- ¿Para quién es este visualizador de Exponenciación Binaria?
- La visualización de Exponenciación Binaria está pensada para nivel intermedio, dentro de la categoría Divide y Vencerás. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Exponenciación Binaria?
- En la misma categoría (Divide y Vencerás) puedes explorar: Tower of Hanoi. Todos tienen visualización interactiva.