leetcode:50.Pow(x, n)

题目描述：

实现 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.0n 是 32 位有符号整数，其数值范围是$[-2^{31},2^{31}-1]$ 。

题目难度：中等

分析：

如果直接调用API的话：return Math.pow(x, n)即可。 计算 x的 n次幂函数也就是计算 n个 x相乘。但是如果直接用for循环计算的话，当 n特别大的时候就会超出时间限制，显然不能这么去计算。但是可以用分治算法的思想把时间复杂度从 $O(n)$ 缩短到 $O(lo{g}_{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(lo{g}_{2}n)$，利用了分治的思想可以缩短用时。