0%

快速幂模板(Python)

首先我们需要知道下面这个公式:
(a^b) mod c=((a mod c)^b) mod c

现在试着用最常规的方法计算 a^b

算法一:

1
2
3
4
5
6
def spow(n, m):
res = 1
for i in range (m):
res *= n
return res
print(spow(2, 100))

显然这个算法的时间复杂度为 O(n),我们需要找到一个复杂度较低的算法。
对于幂次运算,例如a^5

如果直接运算,需要5次循环了。

但是如果写成 a^5 = a*((a^2)^2),如果是这样,就仅仅需要3次运算了,一下子省了两次运算,对于这次次数低的运算都如此可观,对于次数多的运算可想而知了。

对于上面的情况,计算幂的时候,明显需要分情况考虑。

1、当b为偶数的时候,a^b = (a^2)^(b/2);
2、当b为奇数的时候,a^b = a*(a^2)((b-1)/2)。

时间复杂度降到了 O(logn)

算法二:

1
2
3
4
5
6
7
8
9
10
def qpow(n, m):
res = 1
base = n
while m != 0:
if (m&1) != 0:
res = res*base
base = base*base
m = m >> 1
return res
print(qpow(2, 100))

如果要取余

算法三:

1
2
3
4
5
6
7
8
9
10
11
mod = 1000000007
def qpow(n, m):
res = 1
base = n
while m != 0:
if (m&1) != 0:
res = res*base%mod
base = base*base%mod
m = m >> 1
return res
print(qpow(2, 100))
-------------    本文结束  感谢您的阅读    -------------