题目描述
实现函数double Power(double base, int exponent),求base的 exponent次方。
不得使用库函数,同时不需要考虑大数问题。
样例
样例1
输入:10 ,2
输出:100
样例2
输入:10 ,-2
输出:0.01
算法1
(快速幂)
样例给出的幂可能很大,暴力的话会超时,所以建议用快速幂
这里用递归写法也不方便,所以最好用循环写法。
快速幂思想:
任何数都可以用二进制来表示,如17 10001 所以如10^17=10^1*10^16我们可以细化为10^2^0和10^2^4;
所以任何a^b,都可以将他们划分为a^(2^k)、、、a^16、a^8、a^4、a^2、a^1中若干个的乘积。
最后用循环遍历这些乘积,可以发现幂的二进制位为1对应的a^(2^i)就要被选中。
注意
a^(2^k)……、a^8、a^4、a^2、a^1前一项总是等于后一项的平方。
时间复杂度
假设指数是 n,则一共会循环 O(logn) 次,所以时间复杂度是 O(logn)。
参考文献
https://blog.csdn.net/Harington/article/details/87602682
C++ 代码
class Solution {
public:
double Power(double base, int exponent) {
double ran=1.0;
int n=abs(exponent);
while(n){
if(n&1){
ran*=base;
}
base*=base;
n>>=1;
}
if(exponent<0) return 1/ran;
return ran;
}
};