leetcode 50 | 实现pow函数
实现 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/22 = 1/4 = 0.25说明:
- -100.0 < x < 100.0
- n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
计算一个值x的整数n阶乘，其实就是，如果每一步只算一次乘法，则复杂度为O(n)：
算式1：f(x, n)=x^n=x*x*x...*x
如果n为负数，则有：
算式2：f(x, n) = 1/f(x, -n)
对于算式1：
还有如下变形，算法复杂度O(logn)：
算式3：f(x, n) = f(x, n/2) * f(x, n/2)
就比如3的4次方，其实是3的平方乘以3的平方，依据算式3，那么就能写出递归的写法，注意如果n为奇数，n/2取整对丢失1，则有：
算式4：f(x, n) = x * f(x, n/2)* f(x, n/2)
源代码：
static double fast_pow(double x, int n)
{
//特殊处理
if (n == 0) { return 1.0; }
if (n == 1) { return x; }
//计算一半的pow值
double p = fast_pow(x, n / 2);
//n如果是奇数，必然少算了一个x，因此这里乘以x
return n & 1 ? p * p * x : p * p;
}
static double myPow(double x, int n)
{
//正负处理
return n < 0 ? 1 / fast_pow(x, -n) : fast_pow(x, n);
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-01-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读