【算法笔记·数论】快速幂,加速幂运算,超级详细。C/C++

前言:

欢迎光临大千小熊的博客,我是一只又会MMD又会C++的正派熊,B站和CSDN同步更新,欢迎关注。

幂运算含义:

形如 x n x^n xn 指数是x,底数是x的一个幂。( n n n是变量)
例如 2 4 = 16 , 2 2 = 4 2^4=16,2^2=4 24=16,22=4这样的运算。

计算幂运算的方法:

例如,我们想去计算 2 4 2^4 24。我们可以循环4次,另res=1,然后res*=4。
但是这样的算法是不高效率的。
这是因为,我们想计算 2 ∗ 2 ∗ 2 ∗ 2 2*2*2*2 2∗2∗2∗2的时候,人类一般都会用 2 ∗ 2 = 4 2*2=4 2∗2=4,然后是 4 ∗ 4 = 16 4*4=16 4∗4=16。来计算答案,这样只需要两步。这个方法的时间复杂度比上面算法的时间复杂度小,而且是因为拆开成两个部分,因此新的算法复杂度是 l o g ( x ) log(x) log(x)级别的。而最先的那个笨方法是 x x x级别的。

那么我们怎么做到那样的巧妙的方法去计算快速幂呢?
请看下面的内容。

快速幂的设计思想:

例如上面的例子 2 ∗ 2 ∗ 2 ∗ 2 2*2*2*2 2∗2∗2∗2。我们可以设计一个递归函数。来不停的拆分上面的算式。
设函数 Q u i c k P o w ( x , n ) QuickPow(x,n) QuickPow(x,n)表示 x n x^n xn的结果。下一个状态是 Q u i c k P o w ( x ∗ x , n / 2 ) QuickPow(x*x,n/2) QuickPow(x∗x,n/2)。
那么 Q u i c k P o w ( 2 , 4 ) QuickPow(2,4) QuickPow(2,4)意思就是上面的 2 ∗ 2 ∗ 2 ∗ 2 2*2*2*2 2∗2∗2∗2。
然后 Q u i c k P o w ( 4 , 2 ) QuickPow(4,2) QuickPow(4,2)意思是 4 ∗ 4 4*4 4∗4。
最后 Q u i c k P o w ( 16 , 1 ) QuickPow(16,1) QuickPow(16,1)的意思是到此为止。因为第二个参数是1。

看到这里也许你可能还是一头雾水,下面请看这种说法:
例如: 3 ∗ 3 ∗ 3 ∗ 3 ∗ 3 ∗ 3 ∗ 3 ∗ 3 3*3*3*3*3*3*3*3 3∗3∗3∗3∗3∗3∗3∗3。(总共8个3)

我们这样计算 ( 3 ∗ 3 ∗ 3 ∗ 3 ) ∗ 3 ∗ 3 ∗ 3 ∗ 3 (3*3*3*3)*3*3*3*3 (3∗3∗3∗3)∗3∗3∗3∗3先进行一个 3 ∗ 3 3*3 3∗3的运算。所以我们可以说上面的这个方程实际等价于 ( 9 ∗ 9 ) ∗ 3 ∗ 3 ∗ 3 ∗ 3 (9*9)*3*3*3*3 (9∗9)∗3∗3∗3∗3。
最后通过递归到 ( 81 ) ∗ 3 ∗ 3 ∗ 3 ∗ 3 (81)*3*3*3*3 (81)∗3∗3∗3∗3知道81就是一个其中的一个解。然后前面是81,那么后面的 3 ∗ 3 ∗ 3 ∗ 3 3*3*3*3 3∗3∗3∗3也一定是81。所以最终81*81就是我们要的一个解。

再再看看下面这种说法:
Q u i c k P o w ( x , n ) QuickPow(x,n) QuickPow(x,n)的 n n n的意思是有几个 x x x需要相乘。如果 n = 1 n=1 n=1,那么就不需要继续进行相乘了。

小小的疑问:

那如果指数是奇数怎么办呢?
其实和偶数是一样的,奇书/2==偶数/2(“/”的意思是“整除”)。
我们只需要计算完结果然后像这样 x ∗ Q u i c k P o w ( x , n ) x*QuickPow(x,n) x∗QuickPow(x,n)手动的把 x x x多乘一份就可以了。

现在动手试一试吧,我想你一定能搞清楚递归函数是怎么样的。下面请看示例代码:

快速幂(递归)实现代码:

这里我为你准备了两个版本:
版本1:

#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll res = 1;
ll QuickPow(int x, int n) {
    if (n == 1)  //函数的退出条件
        return res *= x;

    if (n % 2 == 0) {  //偶数
        return QuickPow(x * x, n / 2);
    } else {  //基数
        return x * QuickPow(x * x, n / 2);
    }
}

int main() {
    cout << QuickPow(2, 3);
    return 0;
}

版本2:

#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll res = 1;
ll QuickPow(int x, int n) {
    if (n == 0)
        return 1;
    ll res = QuickPow(x * x, n / 2);
    if (n & 1)
        res = res * x;  //发现n是一个奇数,手动乘入x
}

int main() {
    cout << QuickPow(2, 3);
    return 0;
}

快速幂的设计思想2:

那么如果不用递归能不能实现快速幂呢?
答案当然是可以的。
我们设 n = 2 k n=2^k n=2k,为什么底数是 2 2 2呢?这个我们做一个悬念。
那么原来的方程: x n x^n xn可以写成 ( ( x 2 ) 2 ) 2 . . . ((x^2)^2)^2... ((x2)2)2...
只要进行k次那么答案就被我们求出来了。
又因为
【算法笔记·数论】快速幂,加速幂运算,超级详细。C/C++
所以计算机是2进制的世界,我们可以很轻松的操作二进制比如>>。所以将n转为2的倍数然后进而来表示n。
例如计算:
【算法笔记·数论】快速幂,加速幂运算,超级详细。C/C++
我们做一个16次的循环,不停的乘x,然后如果遇到指数是2,4,16(也就是22的二进制中10110为1的部分),就把他们乘入res中,最后就可以得到最终答案。这个方法的只要循环16次,比22次要少了很多。

快速幂(二进制)实现代码:

#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll QuickPow(int x, int n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1 == 1)
            res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
int main() {
    cout << QuickPow(4, 9);
    return 0;
}
上一篇:【DB笔试面试81】在MySQL中,如何查看创建的用户OLDLHR拥有哪些权限?


下一篇:81. 搜索旋转排序数组 II