公式求幂→二分求幂→快速求幂→快速求幂取模
公式求幂
直接使用 C 语言的库函数 pow(),pow()函数在 math 头文件里
当然用公式求解,似乎很简单,但是它的时间复杂度较高,为 O(n),对于数据较大的问题,
十分容易超时
二分求幂
二分幂的时间复杂度相较于第一种有了明显的优化,达到了 O(lgn)
二分求幂的原理可以用下面这张图表示 :
用递归来实现:
int pow(int a,int n)//返回值是 a 的 n 次方
{
if(n==0)//递归终止条件
return 1;
if(n==1)
return a;
int result=pow(a,n/2);//二分递归
result=result*result;//这部分奇数偶数都一样
if(n%2==1)//如果 n 是奇数,就要多乘一次
result=result*a;
return result;
}
用非递归来实现:
int pow(int a,int n)//返回值是 a 的 n 次方
{
int result=1;
while(n!=0)
{
if(n%2==1)//如果 n 是奇数
result=result*a;//就要多乘一次
a=a*a;
n=n/2;//二分
}
return result;