快速幂+相关知识点.docx
需积分: 2 116 浏览量
2024-03-17
23:11:05
上传
评论
收藏 50KB DOCX 举报
公式求幂→二分求幂→快速求幂→快速求幂取模
公式求幂
直接使用 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;
资源评论
