题目描述：
实现 pow(x, n)，即计算 x 的 n 次幂函数。
示例1：
输入: 2.00000, 10 输出: 1024.00000
示例2：
输入: 2.10000, 3 输出: 9.26100
示例3：
输入: 2.00000, -2 输出: 0.25000 解释: 2^-2 = 1/2^2 = 1/4 = 0.25
说明：
- -100.0 < x < 100.0
- n 是 32 位有符号整数，其数值范围是[ − 2 31 , 2 31 − 1 ] 。
题目难度：中等
分析：
如果直接调用API的话：return Math.pow(x, n)即可。
计算 x的 n次幂函数也就是计算 n个 x相乘。但是如果直接用for循环计算的话，当 n特别大的时候就会超出时间限制，显然不能这么去计算。但是可以用分治算法的思想把时间复杂度从 O(n) 缩短到 O(log 2 n) 。简单点来说就是两两相乘，把 n个x分成两部分，比如n为8时，前4后4，那么就变成了x 4 * x 4 ，此时只需要计算一个x 4 的结果然后再和自身相乘即可，同理x 4 也可以拆分成x 2* x 2 ，以此类推，即可大大缩短用时。这里其实有点类似折半查找。
代码如下：
class Solution { public double myPow(double x, int n) { // 判断n是正是负 int pow = n > 0 ? 1 : -1; // 最终结果，定义成1在相乘时不影响结果 double res = 1; // 循环相乘即可，这里利用n的奇偶性来判断 while (n != 0) { if (n % 2 != 0) { res *= x; } x *= x; n /= 2; } // 如果n是负数，这里要把前面的结果取倒数 if (pow == -1) { return 1 / res; } return res; } }
总结：
时间复杂度为O ( l o g 2 n ) ，利用了分治的思想可以缩短用时。
