快速幂

2019-09-09-view(s)-comment(s)- min read

简单来说

其实这是一个很精妙的思路，对比一下就可以发现：

差不多是这样：

python

# 求 a 的 n 次幂，ans 是结果
baseNum,ans = a,a
for i in range(n-1):
    ans *= baseNum

是这样：

python

# 求 a 的 n 次幂，ans 是结果
powerNum,ans = a,1
while not n==0:
    if n&1:ans *= powerNum
    powerNum *= powerNum
    n >>= 1

另外，快速幂的时间复杂度是 O(log₂ⁿ)，而普通幂是 O(n)。