快速幂
2021-10-20 09:09:16 39 举报AI智能生成
快速幂
作者其他创作
大纲/内容
快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以[公式]的时间复杂度计算乘方。
思考
7的10次方，怎样算比较快？
方法1：最朴素的想法，7*7=49，49*7=343，... 一步一步算，共进行了9次乘法。
方法2：先算7的5次方，即7*7*7*7*7，再算它的平方，共进行了5次乘法。
方法3：先算7*7得49，则7的5次方为49*49*7，再算它的平方，共进行了4次乘法。
实现
递归快速幂
思路
二分法，可以得到一个递归方程：
计算a的n次方：
- 如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；
- 如果n是奇数，那么就先计算a的n-1次方，再乘上a；
- 递归出口是a的0次方为1。
实现
//递归快速幂
int qpow(int a, int n)
{
if (n == 0)
return 1;
else if (n % 2 == 1)
return qpow(a, n - 1) * a;
else
{
//这个temp变量是必要的, 不然的话会导致整个算法就退化为O(n)
int temp = qpow(a, n / 2);
return temp * temp;
}
}
int qpow(int a, int n)
{
if (n == 0)
return 1;
else if (n % 2 == 1)
return qpow(a, n - 1) * a;
else
{
//这个temp变量是必要的, 不然的话会导致整个算法就退化为O(n)
int temp = qpow(a, n / 2);
return temp * temp;
}
}
优化
递归虽然简洁，但会产生额外的空间开销。
非递归快速幂
思路
我们把10写成二进制的形式，也就是 （1010）。
现在我们要计算 （1010） ，可以怎么做？
我们很自然地想到可以把它拆分为（1000）+（10）
实际上，对于任意的整数，我们都可以把它拆成若干个（10....）的形式相乘。
7^（1000） 、7^（10）恰好就是7^8、 7^2, 我们只需不断把底数平方就可以算出它们。
实现
//非递归快速幂
int qpow(int a, int n){
int ans = 1;
while(n){
//如果n的当前末位为1
if(n&1){
//ans乘上当前的a
ans *= a;
}
//a自乘
a *= a;
//n往右移一位
n >>= 1;
}
return ans;
}
int qpow(int a, int n){
int ans = 1;
while(n){
//如果n的当前末位为1
if(n&1){
//ans乘上当前的a
ans *= a;
}
//a自乘
a *= a;
//n往右移一位
n >>= 1;
}
return ans;
}
应用
模意义下取幂: 计算 x^k % n.
取模的运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可
实现
//非递归快速幂
int qpow(int a, int n, int mod){
int ans = 1;
while(n){
//如果n的当前末位为1
if(n&1){
//ans乘上当前的a并取模
ans = ans * a % mod;
}
//a自乘并取模
a = a * a % mod;
//n往右移一位
n >>= 1;
}
return ans;
}
int qpow(int a, int n, int mod){
int ans = 1;
while(n){
//如果n的当前末位为1
if(n&1){
//ans乘上当前的a并取模
ans = ans * a % mod;
}
//a自乘并取模
a = a * a % mod;
//n往右移一位
n >>= 1;
}
return ans;
}
0 条评论
下一页
