顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高
为什么可以这样? 因为我们可以采用二分分析
所以我们可以写出递归代码：
int qpow(int n,int a){ if(n ==0) return 1; else if(n%2==1){ // int tmp= qpow(n/2,a); 如果我们直接用这种方式是再次加速了运算 // return tmp*tmp*a; return qpow(n-1,a)*a; }else{ int tmp = qpow(n/2,a); return tmp*tmp; } }
我们换一个角度来引入非递归的快速幂。还是7的10次方，但这次，我们把10写成二进制的形式，也就是
那就是7的上面的次方
也就是7^1 * 7^8
int qpow(int n,int a){ int ans=1; while(n){ if(n&1) ans*=a; a*=a; n>>=1; } return ans; }
计算a^n 只要a的数据类型支持乘法且满足结合律，快速幂的算法都是有效的。 例如矩阵等
Ref：https://zhuanlan.zhihu.com/p/95902286
