题解 | #数值的整数次方#
数值的整数次方
http://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00
描述
这是一篇面对初级coder的题解。
知识点：数学常识 快速幂 递归
难度：一星
题解
题目：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。
即求：浮点数的整数次方
首先补充一些数学上的基础知识：
a0=1 任何数的0次方得1
m-n=(1/m)一个数的负数次方就是一个数的正数次方的倒数
故有下面的预处理函数：
if(exponent==0)
return 1;
if(exponent<0)
{
base=1/base;
exponent=-exponent;
} 方法一：暴力求解
按照乘方的定义 就是连续n个数相乘
class Solution {
public:
double Power(double base, int exponent) {
if(exponent==0)
return 1;
if(exponent<0)
{
base=1/base;
exponent=-exponent;
}
double answer=1 ;//连乘 故初始化为1
for(int i=0; i<exponent;i++)
answer*=base;
return answer;
}
};
运行时间： 8 ms 占用内存：520K
显然，这样执行效率不高 其他语言也类似 需要更好的方法
时间复杂度O(n)
方法二：递归分治的思想
基于的原理如下 若n为偶数 a^n=a^(n/2)*a^(n/2) 若n为奇数 a^n=a^(n/2)*a^(n/2)*a 注意此处的除法为整除 之所以不用除法是为了提高效率
class Solution {
public:
double Power(double base, int exponent) {
if(exponent==0)
return 1;
if(exponent<0)
{
base=1/base;
exponent=-exponent;
}
return Dpower(base,exponent);
}
double Dpower(double b, int n) {
if (n == 1)
return b;
double ret = Dpower(b, n/2);
if (n&1) // 奇数
return ret * ret * b;
else
return ret * ret;
}
};
递归受递归深度限制，同时大家知道，递归虽然简洁，但会产生额外的空间开销。我们可以把递归改写为循环，来避免对栈空间的大量占用
运行时间： 4 ms 占用内存：524K
时间复杂度：O(logn)，每次规模减少一半
空间复杂度：O(logn)，递归栈，因为要记住logn个变量
方法三：快速幂
本质上采用了数的二进制表示方法 如求7的10次方，但这次，我们把10写成二进制的形式，也就是 1010 即10=0*2^0+1*2^1+0*2^2+1*2^3 考虑a(m+n)=am*an 7^10=7^2^1+7^2^3
class Solution {
public:
double Power(double base, int exponent) {
if(exponent==0)
return 1;
if(exponent<0)
{
base=1/base;
exponent=-exponent;
}
double answer = 1;
while(exponent){
if(exponent&1) //如果n的当前末位为1
answer *= base; //ans乘上当前的a
base *= base; //a自乘
exponent >>= 1; //n往右移一位
}
return answer;
}
};
运行时间： 4 ms 占用内存：512K
时间复杂度：O(logn)，因为n的二进制位个数为logn 空间复杂度：O(1)
templateinline T identity_element(plus){
return T(0);
}
templateinline T identity_element(multiplies){
return T(1);
}
templateinline T power_this(T x, Integer n){
return power_this(x, n, multiplies());
}
templateT power_this(T x, Integer n, MonoidOperation op){
if (n == 0)
return identity_element(op);
else{
while ((n & 1) == 0){
n >>= 1;
x = op(x, x);
}
T result = x;
n >>= 1;
while (n != 0){
x = op(x, x);
if ((n & 1) != 0)
result = op(result, x);
n >>= 1;
}
return result;
}
} identity_element(op)为取“证同元素”。所谓“运算op的证同元素”，意思是数值A若与该元素做op运算，会得到A自己。加法的证同元素为0，因为任何元素加上0仍为自己。乘法的证同元素为1，因为任何元素乘以1仍为自己。总结
以2的7次方为例 三种方法总结如下：
可以看做是JZ11的升级版，二进制的数据本身就包含了很多信息
另：数学不好真玩不转计算机
扩展
快速幂的应用广泛
如下面例题中求矩阵的快速幂
阿Q的题解 文章被收录于专栏
阿Q秋招刷过的题
