快速幂

• 1. 利用快速幂优化的时间复杂度
• 2. 快速幂方法及代码
• 3.总结

文章参考自 B站董晓算法

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

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

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

利用快速幂可以做到

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

2. 快速幂方法及代码

我们要求 ana^{n}an (0 <= a,n < 2312^{31}231)

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

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

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

long long quickpow(long long a,int n)
{long long  res = 1; // 这是我们要的结果，因为是乘积，记住开始不要写成0while(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
}

我们来模拟一下

3.总结

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