如何高效计算x的n次方，避免长尾词问题？

本文共计818个文字，预计阅读时间需要4分钟。

目录 + 主题 + 解题思路 - 分情况讨论 + 代码实现 + 解题思路 - 分治 + 代码实现 + 主题 + 主题地址 + 实现pow(x, n)，即计算x的n次幂（即x^n）。 示例： 输入：+x+=+2.00000+, +n+=+10+ 输出：+1024.0+

目录

• 题目
• 解题思路-分情况讨论
• 代码实现
• 解题思路-分治
• 代码实现

题目

题目地址

实现pow(x,n)，即计算x的整数n次幂函数（即，xn）。

示例 1：

输入： x = 2.00000, n = 10

输出： 1024.00000

示例 2：

输入： x = 2.10000, n = 3

输出： 9.26100

示例 3：.

输入： x = 2.00000, n = -2

输出： 0.25000

解释： 2-2 = 1/22 = 1/4 = 0.25

提示：

-100.0 < x < 100.0

-231<= n <= 231-1

-104<= xn<= 104

解题思路-分情况讨论

本题可以分几种情况讨论:\

• 如果 x = 1，那么无论 n 的值是多少，结果都是 1
• 如果 n = 0，那么无论 x 的值是多少，结果都是 1
• 如果 n = 1，那么无论 x 的值是多少，结果都是 x
• 如果 x = -1，那么如果 n 是偶数，结果是 1，否则结果是 -1
• 如果 n > 0，则结果为 1 *= x n 次
• 如果 n < 0，则结果为 1 /= x n 次

代码实现

var myPow = function(x, n) { if(x === 1 || n === 0){ return 1 } if(x===-1){ return n % 2 ? -1 : 1 } let res = 1 if(n>0){ for(let i = 0;i<n;i++){ res *= x } return res } for(let i = 0;i<-n;i++){ res /= x if(x>0 && res<0.000005){ return res } } return res }

解题思路-分治

上面的解题思路虽然能解题，但是因为要真实的进行每一次计算，所以效率比较低。那如何才能提高效率呢？

这里我们可以采用类似二分的方法，将 x 的 n 次方拆分为 x^(n/2) * x^(n/2)，以此来加速计算的过程。每次拆分一半，直到 n = 0。因为每次的处理逻辑是相同的，所以可以利用递归函数递归调用自己，而退出条件就是 n = 0。

var myPow = function(x, n) { if(n == 0){ return 1 } if(n < 0){ return 1 / myPow(x, -n) } if(n % 2){ return x * myPow(x, n - 1) } return myPow(x * x, n / 2) }

至此我们就完成了leetcode-50-Pow(x, n)，更多关于前端算法 Pow(x, n)题解的资料请关注易盾网络其它相关文章！