剑指 Offer 16. 数值的整数次方
力扣题目链接[1]
实现 pow(x, n)，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。
示例 1：
代码语言：javascript复制输入：x = 2.00000, n = 10
输出：1024.00000
「提示：」
100.0 < x < 100.0231 <= n <= 2311104 <= xn <= 104
思路：
首先考虑使用循环来不断进行相乘。如果 n 是负数，则最终求出倒数即可。不难写出如下代码：
循环
代码语言：javascript复制/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {
let res = 1;
for (let i = 0; i < Math.abs(n); i ) {
res *= x;
}
return n < 0 ? 1 / res : res;
};
- 时间复杂度 O(n)。
- 空间复杂度 O(1)。
分析：
这样处理确实简单粗暴，但是无法通过提交。因为当n很大的时候，会进行太多次的循环次数，最终就会超出时间限制。因此此方法「不可取」。
二分法
通过二分的方式可以将时间复杂度由O(N)降低至O(logN) 。二分法的思路是：
- 如果指数
n为偶数，那么x^n就等同于(x^2)^(n/2) - 如果指数
n为奇数，那么x^n就等同于x(x^2)^(Math.floor(n/2))，外层的指数是向下取整 - 奇偶数可以通过
n & 1是否等于 1 判断，等于 1 就是奇数，等于 0 就是偶数 - 指数除以 2 并向下取整可以通过
n >> 1
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {
if (n === 0) return 1; // 特殊情况处理
if (n === 1) return x;
if (n === -1) return 1 / x;
let result = myPow(x, n >> 1); // 计算指数除以2并向下取整的结果
result *= result; // 结果进行平方
if ((n & 1) === 1) result *= x; // 如果n是奇数则结果再乘以x
return result;
};
- 时间复杂度 O(logn)。
- 空间复杂度 O(1)。
分析：
首先处理一些极值情况。尤其是第三条，当n === -1时，直接返回倒数。这样就不用事先处理 n 到底是正数还是负数的情况。因为如果n是负数，那么不断执行n >> 1就会执行到n === -1的情况。
然后对指数进行除以 2 并向下取整计算出结果，对结果进行平方处理。如果说n就是偶数，那么上述的两步操作和不对指数进行除以 2 直接计算得出的结果是一样的。如果说n是奇数，需要再对结果乘以x，两者才相等。
如此计算，就可以将时间复杂度降低至O(logn)。同样是相乘，x相乘n次和x相乘(n / 2)次再将结果相乘，后者可以降低指数级的相乘次数，所以此方法可以大幅降低相乘的次数，最终也不会超时。
总结
本题采用二分法的思想进行题解。逐个相乘是最笨的办法，但是无法通过提交，因此不能使用。二分法可以大大的降低重复相乘的次数，并且可以确保不会超时。
复杂度方面，二分的时间复杂度为对数级别。result变量占用常数级别大小的额外空间。
参考资料
[1]
力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/57rwmg/
