从化网站建设服务,资质做网站需要用到什么,网站 百度认证,产品品牌推广公司首先我们需要知道下面这个公式#xff1a; (a^b) mod c((a mod c)^b) mod c
现在试着用最常规的方法计算 a^b
算法一#xff1a;
def spow(n, m):res 1for i in range (m):res * nreturn res
print(spow(2, 100))显然这个算法的时间复杂度为 O(n)#xff0c;我们需要找到…首先我们需要知道下面这个公式 (a^b) mod c((a mod c)^b) mod c
现在试着用最常规的方法计算 a^b
算法一
def spow(n, m):res 1for i in range (m):res * nreturn res
print(spow(2, 100))显然这个算法的时间复杂度为 O(n)我们需要找到一个复杂度较低的算法。 对于幂次运算例如a^5
如果直接运算需要5次循环了。
但是如果写成 a^5 a*((a2)2)如果是这样就仅仅需要3次运算了一下子省了两次运算对于这次次数低的运算都如此可观对于次数多的运算可想而知了。
对于上面的情况计算幂的时候明显需要分情况考虑。
1、当b为偶数的时候a^b (a2)(b/2) 2、当b为奇数的时候a^b a*(a^2)((b-1)/2)。
时间复杂度降到了 O(logn)
算法二
def qpow(n, m):res 1base nwhile m ! 0:if (m1) ! 0:res res*basebase base*basem m 1return res
print(qpow(2, 100))如果要取余
算法三
mod 1000000007
def qpow(n, m):res 1base nwhile m ! 0:if (m1) ! 0:res res*base%modbase base*base%modm m 1return res
print(qpow(2, 100))
