快速幂

misaka10032

发布于：Apr 4, 2021

次浏览

「快速幂算法」，存在递归和迭代两个版本。

「快速幂算法」的本质是分治算法。举个例子，如果我们要计算 x^64，我们可以按照：
x ->x^2->x^4->x^8->x^16->x^32->x^64的顺序，从x开始，每次直接把上一次的结果进行平方，计算6次就可以得到 x^64 的值，而不需要对x乘63次。
再举一个例子，如果我们要计算 x^77，我们可以按照：
x->x^2->x^4->x^9->x^19->x^38->x^77的顺序,但是在x^4->x^9这一步骤中，我们把上一次的结果进行平方后，还要额外乘一个x。
直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘x。但如果我们从右往左看，分治的思想就十分明显了：
·当我们要计算 x^n时，我们可以先递归地计算出 y = x^floor(n/2)，其中floor(a)表示对a进行下取整；
·根据递归计算的结果，如果n为偶数，那么 x^n = y^2 ；如果n为奇数，那么 x^n = y^2*x;
·递归的边界为n=0，任意数的0次方均为1。
由于每次递归都会使得指数减少一半,因此递归的层数为O(logn),算法可以在很快的时间内得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
double quick(double x,long long n)
{
    if(n==0)  return 1.0;
    double y=quick(x,n/2);
    if(n%2==0)  return y*y;
    else        return y*y*x;
}
    double myPow(double x, int n) {
    long long N=n;
    if(N>=0)   return quick(x,N);
    else       return 1.0/quick(x,-N);
    }
};

由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。在方法一中，我们也提到过，从左到右进行推导是不容易的，因为我们不知道是否需要额外乘x。但我们不妨找一找规律，看看哪些地方额外乘了x，并且它们对答案产生了什么影响。

这样以来，我们从x开始不断地进行平方,如果n的第k个（从右往左，从0开始计数）二进制位为1，那么我们就将对应的贡献 x^2^k计入答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
double quick(double x,long long n)
{
    double ans=1.0;
    double contribution=x;
    while(n>0)
    {
        if(n%2==1)   ans=ans*contribution;
        contribution=contribution*contribution;
        n=n>>1;
    }
    return ans;
}
    double myPow(double x, int n) {
    long long N=n;
    if(N>=0)   return quick(x,N);
    else       return 1.0/quick(x,-N);
    }
};

end☆~

更新于：Apr 4, 2021

算法

c++