推广 热搜: 铸铁T型槽平台  封号  BQG250/0.3气动隔膜泵  北京  收购ACF  手中  牵手  滤芯  动词  清扫器刮刀 

快速幂 、快速幂时间复杂度

   日期:2023-04-02     浏览:26    评论:0    
核心提示:快速幂算法计算 。 可以看到,原本需要12次乘法的计算,现在只需要5次乘法了。 将 的上标全写为二进制可以看到,完全展开之后, 的上标组成的二进制串正是 的二进制串。真正进行计算时, 可

快速幂算法

计算 。

可以看到,原本需要12次乘法的计算,现在只需要5次乘法了。

将 的上标全写为二进制

可以看到,完全展开之后, 的上标组成的二进制串正是 的二进制串。真正进行计算时, 可以省略。因此,用快速幂算法计算 时,需要进行 次平方运算和 次乘法运算,其中 是 的二进制位数, 是 的二进制中的 的个数。平方运算其实就是乘法运算,因此,需要进行的乘法运算次数总计为 ,介于 倍 之间。因此,快速幂算法的时间复杂度为

快速幂算法还可以像下面这样表述,时间复杂度与上面的一致。不过测试表明,比上面的要慢。

可以看到,尽管大数乘法并非 ,快速幂算法依然要比普通算法快得多。

计算机快速计算2^N是如何实现的?

计算乘方是有快速算法的,并不是一个一个蛮力乘上去的。比如想算2^10000,计算机先算2^5000,再算一次平方,即两个数的乘法。而为了计算2^5000,计算机会先算2^2500再算一次平方。这个算法叫快速幂算法,对于2^N的计算,如果认为每次乘法的时间复杂度是O(1)的话,那整体的时间复杂度只有O(logN)级别。

一般来说,为了实现快速幂算法,首先把指数做二进制表示,比如你要算A的23次方,可以把23分解为16+4+2+1。然后计算B=A^2,C=B^2=A^4,D=(C^2)^2=A^16。最终结果为ABCD相乘。

但这里乘法的复杂度并不是O(1),因为它是无限精度的,也就是所谓的大数乘法。大数乘法也有很多算法,最朴素的,类似手算的方法,复杂度是O(N^2),其他一些方法有分治法,复杂度O(N^1.58),FFT方法,复杂度O(N logN loglogN)等。快速幂的O(logN)次大数乘法中,最复杂的只有最后一次,也就是2^5000的那次,前面的复杂度几何级数衰减,所以整体复杂度也就是最后一次计算的复杂度。如果你用FFT方法的话,复杂度也就是比线性多了一点点,一般计算机上随便算算就出来了。

CPU没有全速运行是因为这个程序只用了1个核心在做计算,而你显示的是总的使用率,所以大概会保持在四分之一的水平。

是否用到了移位操作涉及Python大数运算的具体设计,我不是很懂就不多讲了。但原理上讲也是很有可能的,如果用比特串存储大数的话,那么计算2^N只需要在数组的第N位设置一个1,其余设置为0即可,那么转换到十进制是这段代码中最消耗计算量的部分。

快速幂算法原理

快速幂

顾名思义,快速幂就是快速算底数的n次幂。其时间复杂度为 O(log2N), 与朴素的O(N)相比效率有了极大的提高。

中文名

快速幂

外文名

Fast Power

时间复杂度

log(n)

性质

快速算底数的n次幂

快速

导航

实现

代码比较

原理

快速幂算法的核心思想就是每一步都把指数分成两半,而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小,所需要执行的循环次数也变小,而最后表示的结果却一直不会变。

让我们先来看一个简单的例子:

3^10=3*3*3*3*3*3*3*3*3*3

3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)

3^10=(3*3)^5

3^10=9^5

9^5=(9^4)*(9^1)

9^5=(9^4)*(9^1)

9^5=(6561^1)*(9^1)

以下以求a的b次方来介绍[1]

把b转换成二进制数。

该二进制数第i位的权为

例如

11的二进制是1011

因此,我们将a11转化为算

实现

快速幂可以用位运算来实现

b and 1{也就是取b的二进制***位(即第0位) 判断b是否为奇数,是则为1}

b shr 1{就是去掉b的二进制***位(即第0位)}

C++实现为

b 1//取b二进制的***位,判断和1是否相同,相同返回1,否则返回0,可用于判断奇偶

b1//把b的二进制右移一位,即去掉其二进制位的***位

以下为pascal的实现:

var a,b,n:int64;

function f(a,b,n:int64):int64;

var t,y:int64;

begin

t:=1; y:=a;

while b0 do begin

if(b and 1)=1 then t:=t*y mod n;

y:=y*y mod n;{这里用了一个技巧,y*y即求出了a^(2^(i-1))不知道这是什么的看原理

a^(2^(i-1))*a^(2^(i-1))=a^(2^i)

而且一般情况下a*b mod c =(a mod c)*(b mod c) mod c}

b:=b shr 1;{去掉已经处理过的一位}

end;

exit(t);

end;

begin

read(a,b,n);{n是模}

writeln(f(a,b,n));

end.

[1]

以下为C的实现,为了方便与pascal的对照,变量全部与上面相同.可以对照查看。

递归版:[2]

ll pow(ll a,ll i){

if (i==0) return 1;

int temp=pow(a,i1);

temp=temp*temp%MOD;

if (i1) temp=(ll)temp*a%MOD;

return temp%MOD;

}

非递归版:

ll f(ll a,ll b,ll n){

int t,y;

t=1; y=a;

while (b!=0){

if (b1==1) t=t*y%n;

y=y*y%n; b=b1;

}

return t;

}

如何计算快速幂,比如 x^100000000次方,直接循环很慢。。谢谢了

因为 x^n = (x^(n/2))^2

根据这个公式,可以在 log2N时间内算出乘法幂

递归算法:

int pow(int x,int n)

{

if(n==1) return x;

else if(n1) //n is odd

{

return x*pow(x,n/2);

}

else

{

return pow(x,n/2);

}

}

非递归算法:

int pow(int x,int n)

{

int temp(x),res(1);

while(n)

{

if(n1)

{

res *= temp;

}

temp *= temp;

n=1;

}

return res;

}

快速幂是什么?

解释一下a^b mod c:

a^b mod c=a^(f[0]*2^0+f[1]*2^1+f[2]*2^2...f[t]*2^t)

因为 a*b mod c= ((a mod c) *b) mod c

所以

a^b mod c=(((f[0]*2^0 mod c)*f[1]*2^1 mod c)......*f[t]*2^t mod c)

用这种方法解决a^b mod c 时间复杂度

2^t=b2^(t+1)

t=log(2)bt+1

因为 b是个整数 所以

t=log(2)b

时间复杂度比直接循环求a^b大大的降低了

模取幂运算

事实上,m^e mod n可以直接计算,没有必要先算m^e。

m^e mod n叫做模取幂运算,根据简单的数论知识,很容易设计一个分治算法。具体如下:

设b[k], b[k-1],...,b[1],b[0]是整数b的二进制表示(即b的二进制有k+1位,b[k]是最

高位),下列过程随着c的值从0到b成倍增加,最终计算出a^c mod n

Modular-Exponentiation(a, b, n)

1. c ← 0

2. d ← 1

3. 设b[k],b[k-1],..b[0]是b的二进制表示

4. for i←k downto 0

5. do c ← 2c

6. d ← (d*d) mod n

7. if b[i] = 1

8. then c ← c + 1

9. d ← (d*a) mod n

10. return d

首先说明一下,上述伪代码中用缩紧表示语句之间的层次关系,例如第5~9行都是for循环体

内的语句,第8~9行都是then里面的语句。这是我比较喜欢的一种表示方法 ;)

上述伪代码依次计算出的每个幂或者是前一个幂的两倍,或者比前一个幂大1。过程依次从

右到左逐个读入b的二进制表示已控制执行哪一种操作。循环中的每次迭代都用到了下面的

两个恒等式中的一个:

a^(2c) mod n = (a^c mod n)^2

a^(2c+1) mod n = a * (a^c mod n)^2

用哪一个恒等式取决于b[i]=0还是1。由于平方在每次迭代中起着关键作用,所以这种方法

叫做“反复平方法(repeated squaring)”。在读入b[i]位并进行相应处理后,c的值与b的

二进制表示b[k],b[k-1],..b[0]的前缀的值相同。事实上,算法中并不真正需要变量c,

只是为了说明算法才设置了变量c:当c成倍增加时,算法保持条件d = a^c mod n 不变,直

至c=b。

如果输入a,b,n是k位的数,则算法总共需要执行的算术运算次数为O(k),总共需要执行的位

操作次数为O(k^3)。

关于快速幂和快速幂时间复杂度的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。

原文链接:http://www.yzhs.net/news/show-10852.html,转载和复制请保留此链接。
以上就是关于快速幂 、快速幂时间复杂度全部的内容,关注我们,带您了解更多相关内容。
 
标签: 复杂度 算法 快速
打赏
 
更多>同类资讯
0相关评论

推荐资讯
网站首页  |  VIP套餐介绍  |  关于我们  |  联系方式  |  使用协议  |  版权隐私  |  SITEMAPS  |  网站地图  |  排名推广  |  广告服务  |  积分换礼  |  网站留言  |  RSS订阅  |  违规举报