¿Por qué 'code01' es más eficiente que 'code02'? parece que ambos códigos aún obtienen el resto después de que finalizó toda la operación.
// code01 function power(base, exponent) { if (exponent === 0) return 1; const half = parseInt(exponent / 2); const temp = power(base, half); const result = (temp * temp) % 94906249; if (exponent % 2 === 1) return (base * result) % 94906249; else return result; } //code02 function power(base, exponent) { if (exponent === 0) return 1; return base * power(base, exponent - 1) % 94906249; }El primero usa exponent / 2 en la recursión, el segundo exponent - 1 .
La división repetida le da un tiempo de ejecución logarítmico, la resta repetida le da un tiempo de ejecución lineal.
Comparar:
| división | sustracción |
|---|---|
| 8 | 8 |
| 4 | 7 |
| 2 | 6 |
| 1 | 5 |
| . | 4 |
| 3 | |
| 2 | |
| 1 | |
| . |
La división con un factor de 2 significa 4 pasos para la entrada 8, 5 pasos para la entrada 16, 11 pasos para la entrada ~1000. La resta de 1 significa 1000 pasos para la entrada 1000. 11 es mucho menos que 1000.