【算法篇-数论】快速幂

文章参考自 B站董晓算法

1. 利用快速幂优化的时间复杂度

所谓的快速幂就是快速计算底数的n次幂
1

暴力求幂的话时间复杂度为O（n）

利用快速幂可以做到

时间复杂度为 O(log₂n)

2. 快速幂方法及代码

我们要求 $a^n$ (0 <= a,n < $2^{31}$)

快速幂需要用到的思想是 二进制 和 倍增思想

比如 $3^{13}$ = $3^{(1101)}$ = $3^8$ * $3^4$ * $3^1$ ，这是二进制思想，把指数先换成二进制，然后找到1的位置，1的位置决定了是指数的多少次方，然后连乘即可。

还有就是倍增思想，
对 a 做平方倍增，比如，$3^1$,$3^2$,$3^4$,$3^8$,$3^{16}$…
为什么要做这样的倍增？
因为二进制里面，从右往左，就是平方倍增。
我们按照二进制的方法拆分，得到的一定是1，2，4，8…这样的值
我们一步一步往下算，$3^{(1101)}$ 只要二进制指数的位置是 1 就可以直接乘。
不理解没关系，直接看代码分析或许就明白了。

long long quickpow(long long a,int n)
{
    long long  res = 1; // 这是我们要的结果，因为是乘积，记住开始不要写成0
    while(n)//当指数n不为0时，就循环，因为我们每一次都让n >>= 1,相当于 n / 2
    {
        if(n & 1) res = res * a;//如果对应的二进制是1，就乘底数，否则不用计算
        a = a * a; //底数倍增
        n >>= 1;//n往右进一位，方便上面的 n & 1
    }
    return res; // 返回结果就是 a^n
}
1
2
3
4
5
6
7
8
9
10
11

我们来模拟一下

3.总结

以上就是快速幂的方法以及代码
时间复杂度从O(n),优化到O(log₂n)，是一种非常优秀的算法。
大家可以感受一下算法的美