比较容易想到的快速求幂算法使用分治法，这样的时间复杂度是，但使用动态规划的算法比较巧妙。这个算法的思路是根据指数的二进制表示，将其表示成的乘积，同时用循环将制成数组，从程序可以看出，这样做的时间复杂度也是，同时最后显示了与c++中库函数的结比较容易想到的快速求幂算法使用分治法，这样的时间复杂度是，但使用动态规划的算法比较巧妙。这个算法的思路是根据指数的二进制表示，将其表示成的乘积，同时用循环将制成数组，从程序可以看出，这样做的时间复杂度也是，同时最后显示了与c++中库函数的结果对比
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
template<typename T>
T dynamicPlanPow(T x,int n)
{
T result=1;
vector<T> arr;
(x);
int pos=0;
int judge=n&1;
if(judge==1)
{
result*=arr[pos];
}
n=n>>1;
while(n!=0)
{
(arr[pos]*arr[pos]);
pos++;
judge=n&1;
if(judge==1)
{
result*=arr[pos];
}
n=n>>1;
}
return result;
}
void main()
{
double x=2;
int n=100;
printf("%.2lf\n\n%.2lf\n",dynamicPlanPow(x,n),pow(x,n));
}
不用递归的快速求幂算法 来自淘豆网m.daumloan.com转载请标明出处.
