LeetCode50.Pow(x, n)
题目要求
实现 pow(x, n) ,即计算 x
的整数 n
次幂函数(即x的n次方)。
破题思路
快速幂算法
求x的n次方最简单的方法是写一个n次的循环,每一次循环乘以一个x,那这样的话时间复杂度就是n。
快速幂法可以将时间复杂度下降到logn。
以下将从二进制和二分法两个角度进行解析
二进制角度
利用十进制数字 n 的二进制表示,可对快速幂进行数学化解释。
对于十进制整数n,可以化为二进制bm...b3b2b1;
则有二进制转十进制,(二进制转十进制的公式)
那么对于x的n次方,则有
,展开就是
所以根据以上推导,可以把求x的n次方转化成求上面那条公式的积。
所以,我们现在就要做的是两件事:
- 求出x²,x4,x的2m-1次方的值
- 求出b1,b2,b3的值。
所以在循环中,我们要求x的2的n次幂的话,就执行x = x²就行。
取bi的话,循环执行以下操作即可。
- n&1 (与操作): 判断 n 二进制最右一位是否为 1 ;
- n>>1 (移位操作): n 右移一位(可理解为删除最后一位)。
b的值只有两种情况,0和1,如果是1的话那就是x的2的某一个次方,0的话那就是1,用公式表示是这样的。
举个小例子。
分治法角度
快速幂实际上是分治思想的一种应用。
令 n/2 为整数,则需要分为奇偶两种情况(设向下取整除法符号为 "//" ):
观察发现,当 n 为奇数时,二分后会多出一项 x 。
幂结果获取
- 根据推导,可通过循环 x=x2 操作,每次把幂从 n 降至 n//2 ,直至将幂降为 0 ;
- 设 res=1 ,则初始状态 xn=xn×res 。在循环二分时,每当 n 为奇数时,将多出的一项 x 乘入 res ,则最终可化至 xn=x0×res=res,返回 res 即可。
转化为位运算则是
- 取余数 n%2 等价于 判断二进制最右位 n&1 ;
- 向下整除 n//2 等价于 右移一位 n>>1 ;
算法流程
-
当 x=0.0 时:直接返回 0.0 ,以避免后续 1 除以 0 操作报错。分析: 数字 0 的正数次幂恒为 0 ; 0 的 0 次幂和负数次幂没有意义,因此直接返回 0.0 即可。
- 初始化 res=1 。
- 当 n<0 时:把问题转化至 n≥0 的范围内,即执行 x=1/x ,n=−n 。
- 循环计算:当 n=0 时跳出。
- 当 n&1=1 时:将当前 x 乘入 res (即 res∗=x )。
- 执行 x=x2 (即 x∗=x )。(给下一项)
- 执行 n 右移一位(即 n>>=1)。
5.返回res
class Solution {
public double myPow(double x, int n) {
if(x == 0.0f){
return 0.0d;
}
long b = n;
double res = 1.0d;
//如果n<0,则按照幂小于0的方式来进行计算
if(b < 0){
x = 1 / x;
b = -b;
}
while(b > 0){
//首先处理n的低位
if((b & 1) == 1){
//如果低位为1,则进行计算
//如果低位为0,那么结果是1,什么数的0次方都是1,可忽略
res = res * x;
}
//下一项的x底数是上一项的平方
x = x * x;
//n右移一位
b >>= 1;
}
return res;
}
}
手写流程
原文地址:https://blog.csdn.net/Katharsis_2021/article/details/142878585
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!