快速幂乘法
本次我们来讲述快速幂乘法
- 快速幂乘法相对于普通的乘法有很大的时间复杂度优化，其原因是基于位运算的一种算法，空间复杂度能够减少到O( log N )级别。而普通的乘法，则是O( N ) 级别。
下面来看一下代码：
#include<iostream>
using namespace std;
typedef long long ll;
ll Quick_Multi(ll a, ll b);
int main()
{
ll a, b;//a的b次幂
cout << "请输入a的几次方(a^b)" << endl;
cin >> a >> b;
cout << Quick_Multi(a, b) << endl;
return 0;
}
ll Quick_Multi(ll a, ll b)
{
ll ans = 1;
if (!a)//判断a是否为零，如若是0，返回0
return a;
while (b)
{
if (b & 1)//进行与一操作
ans *= a;
a *= a;
b >>= 1;//b向右移以为
}
return ans;
}代码解释
- 首先来看一下快速幂的函数。该函数需要两个参数，a和b。a为底，b为次幂，所计算的结果为a^b。
- 在该代码中，使用了位运算右移和与。如果对于位运算不熟悉，可以上网查询一下。
- 基本思路：我们以a为底，b为次幂，那么我们把b拆分为二进制数。举个例子: 2^7= 128； 那么我们把3拆分成二进制数，为0011,那么我们便有了2^(0011)₂，也就是化成为(2 ^ 4) * ( 2 ^ 2 ) *（ 2 ^ 1 ）的形式。
- 这个拆分的方法类似于分治。利用这个方法，可以把算法复杂度从 O( n )级别降低到O( long n )级别。
优质内容筛选与推荐>>在一般的思路中，好比方我们求 2^7，那么普通的乘法就是 2 * 2 * 2 * 2 * 2 * 2 * 2 求了七次，而是用快速幂乘法，那么也就有了(2 * 2 * 2 ) * ( 2 * 2 * 2 ) * 2 =( ( 2 * 2 * 2 ) ^ 2 ) * 2，另外一个角度去看，乘了3次乘法运算。也就是说，我们把需要乘七次的乘法降低到了成三次。这就是快速幂乘法的意义。
1、Hadoop 3.0.3 + Hive3.0安装
2、JS系列
3、向linux服务器上传下载文件方式收集
4、[leetcode] 242. Valid Anagram
5、Ubuntu14.04配置jdk1.8.0_25，可切换版本