Presta atención porque en este tutorial vas a encontrar el hallazgo que buscas.
Solución:
Empecemos con algunas operaciones matemáticas:
- Para un n positivo, aⁿ = a⨯a⨯…⨯an veces
- Para un n negativo, aⁿ = ⅟a⁻ⁿ = ⅟(a⨯a⨯…⨯a). Esto significa un no puede ser cero.
- Para n = 0, aⁿ = 1, incluso si un es cero o negativo.
Entonces, comencemos desde el caso n positivo y trabajemos desde allí.
Como queremos que nuestra solución sea recursiva, tenemos que encontrar una forma de definir aⁿ en función de una n más pequeña y trabajar a partir de ahí. La forma habitual en que la gente piensa en la recursividad es tratar de encontrar una solución para n-1 y trabajar a partir de ahí.
Y de hecho, dado que es matemáticamente true que aⁿ = a⨯(aⁿ⁻¹), el enfoque ingenuo sería muy similar al que creaste:
public static int pow( int a, int n)
if ( n == 0 )
return 1;
return ( a * pow(a,n-1));
Sin embargo, la complejidad de esto es O(n). ¿Por qué? Porque para n=0 no hace ninguna multiplicación. Para n=1, hace una multiplicación. Para n=2, llama a pow(a,1), que sabemos que es una multiplicación, y la multiplica una vez, por lo que tenemos dos multiplicaciones. Hay una multiplicación en cada paso de recurrencia y hay n pasos. Entonces es O(n).
Para hacer este O(log n), necesitamos que cada paso se aplique a un fracción de n en lugar de solo n-1. Aquí nuevamente, hay un hecho matemático que puede ayudarnos: an₁+n₂ = unn₁⨯an₂.
Esto significa que podemos calcular aⁿ comon/2⨯an/2.
Pero, ¿qué sucede si n es impar? algo como a⁹ será un4.5⨯a4.5. Pero aquí estamos hablando de potencias enteras. Manejar fracciones es algo completamente diferente. Afortunadamente, podemos formularlo como a⨯a⁴⨯a⁴.
Entonces, para un número par usa unn/2⨯an/2y para un número impar, use a⨯ an/2⨯an/2 (división de enteros, dándonos 9/2 = 4).
public static int pow( int a, int n)
if ( n == 0 )
return 1;
if ( n % 2 == 1 )
// Odd n
return a * pow( a, n/2 ) * pow(a, n/2 );
else
// Even n
return pow( a, n/2 ) * pow( a, n/2 );
Esto realmente nos da los resultados correctos (para un n positivo, eso es). Pero, de hecho, la complejidad aquí es, nuevamente, O(n) en lugar de O(log n). ¿Por qué? Porque estamos calculando las potencias dos veces. Lo que significa que en realidad lo llamamos 4 veces en el siguiente nivel, 8 veces en el siguiente nivel, y así sucesivamente. El número de pasos de recursión es exponencial, por lo que esto se cancela con el supuesto ahorro que hicimos al dividir n por dos.
Pero, de hecho, solo se necesita una pequeña corrección:
public static int pow( int a, int n)
if ( n == 0 )
return 1;
int powerOfHalfN = pow( a, n/2 );
if ( n % 2 == 1 )
// Odd n
return a * powerOfHalfN * powerOfHalfN;
else
// Even n
return powerOfHalfN * powerOfHalfN;
En esta versión, estamos llamando a la recursividad solo una vez. Así que pasamos de, digamos, una potencia de 64, muy rápidamente a través de 32, 16, 8, 4, 2, 1 y listo. Solo una o dos multiplicaciones en cada paso, y solo hay seis pasos. Esto es O (registro n).
La conclusión de todo esto es:
- Para obtener un O(log n), necesitamos una recursividad que funcione en una fracción de n en cada paso en lugar de solo n – 1 o n – cualquier cosa.
- Pero la fracción es sólo una parte de la historia. Debemos tener cuidado de no llamar a la recursividad más de una vez, porque usar varias llamadas recursivas en un solo paso crea una complejidad exponencial que se cancela con el uso de una fracción de n.
Finalmente, estamos listos para encargarnos de los números negativos. Simplemente tenemos que obtener el recíproco ⅟a⁻ⁿ. Hay dos cosas importantes a tener en cuenta:
- No permita la división por cero. Es decir, si obtuviste a=0, no debes realizar el cálculo. En Java, lanzamos una excepción en tal caso. La excepción preparada más adecuada es IllegalArgumentException. Es una RuntimeException, por lo que no necesita agregar un
throwscláusula a su método. Sería bueno si lo atraparas o evitaras que tal situación sucediera, en tumaincuando lees los argumentos. - Ya no puede devolver un número entero (de hecho, deberíamos haber usado
longporque nos encontramos con un desbordamiento de enteros para potencias bastante bajas conint) – porque el resultado puede ser fraccionario.
Así que definimos el método para que devuelva el doble. Lo que significa que también tenemos que arreglar el tipo de powerOfHalfN. Y aqui esta el resultado:
public static double pow(int a, int n)
if (n == 0)
return 1.0;
if (n < 0)
// Negative power.
if (a == 0)
throw new IllegalArgumentException(
"It's impossible to raise 0 to the power of a negative number");
return 1 / pow(a, -n);
else
// Positive power
double powerOfHalfN = pow(a, n / 2);
if (n % 2 == 1)
// Odd n
return a * powerOfHalfN * powerOfHalfN;
else
// Even n
return powerOfHalfN * powerOfHalfN;
Tenga en cuenta que la parte que maneja una n negativa solo se usa en el nivel superior de la recursividad. Una vez que llamamos pow() recursivamente, siempre es con números positivos y el signo no cambia hasta que llega a 0.
Esa debería ser una solución adecuada para su ejercicio. Sin embargo, personalmente no me gusta el if allí al final, así que aquí hay otra versión. ¿Puedes decir por qué esto está haciendo lo mismo?
public static double pow(int a, int n)
if (n == 0)
return 1.0;
if (n < 0)
// Negative power.
if (a == 0)
throw new IllegalArgumentException(
"It's impossible to raise 0 to the power of a negative number");
return 1 / pow(a, -n);
else
// Positive power
double powerOfHalfN = pow(a, n / 2);
double[] factor = 1, a ;
return factor[n % 2] * powerOfHalfN * powerOfHalfN;
No se te olvide mostrar esta noticia si lograste el éxito.