关于快速幂算法有效性的证明

本文主要是介绍关于快速幂算法有效性的证明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在读这篇文章之前，请确保已经完全明白二进制基础以及其他与本文相关的二进制的知识

首先，假设我们要求 $3^{101}$ ，设a=3，b=101
将b转化为二进制表示，则为：1100101
通过二进制基础，我们知道： $b=2^{0}+2^{2}+2^{5}+2^{6}=101$ ， $101=2^{0}+2^{2}+2^{5}+2^{6}$
通过乘法原理，我们知道： $3^{c}*3^{d}=3^{c+d}$ ， $3^{c+d}=3^{c}*3^{d}$
因此，可以推出： $3^{101}=3^{2^{0}}*3^{2^{2}}*3^{2^{5}}*3^{2^{6}}=3^{1}*3^{4}*3^{32}*3^{64}=3^{101}$
那么，我们想象一下：如果计算 $2^{x}$ （设x为任意数）的时间复杂度为O(1)，则计算 $3^{101}$ 的时间复杂度就成为了O(6)，也就是 $O({log_{2}}^{101})$
也就是说，计算 $p^{n}$ 的时间复杂度也就成为了 $O({log_{2}}^{n})$

那么，接下来的问题就是：怎么将计算 $2^{x}$ 的时间复杂度降为O(1).

我们的思路是：首先，我们回避掉直接计算 $2^{x}$ 这个问题。因为在对一个数g进行右移的过程中，假设每次右移一位，则一共需要右移 ${log_{2}}^{g}$ 次（如果不熟悉这里可以自己手写验证一下）.那么，在将在指数右移的过程中加上递推即可完成快速幂的运算。

理论部分完毕，下面是具体实现。

#include<cstdio>
#include<iostream>
using namespace std;
int poww(int,int);
int main(){cout<<poww(2,101)<<endl;
}
int poww(int a,int b){int ans=1;while(b!=0){if(b&1){//如果目前b的最后一位为1ans*=a;//向结果赋值（递推的部分）（这里a直接加入了ans的运算）}a*=a;//（a间接加入ans的运算）这里会在文章下面解释b=b>>1;//指数右移一位}return ans;
}
//该代码仅作参考，由于2^101超过了int的范围，实际上无法输出最终结果（但在不超范围的情况下可以正常使用）

因为乘法的时间复杂度是O(1)，所以快速幂的时间复杂度O(logN)成立