首页 > 其他 > 详细

快速幂乘法

时间:2019-06-25 13:45:03      阅读:197      评论:0      收藏:0      [点我收藏+]

本次我们来讲述快速幂乘法

  • 快速幂乘法相对于普通的乘法有很大的时间复杂度优化,其原因是基于位运算的一种算法,空间复杂度能够减少到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次乘法运算。也就是说,我们把需要乘七次的乘法降低到了成三次。这就是快速幂乘法的意义。

快速幂乘法

原文:https://www.cnblogs.com/Yunrui-blogs/p/11082202.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!