本文共 686 字，大约阅读时间需要 2 分钟。

快速幂

简单来说

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

Show Me The Code

普通幂

差不多是这样：

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

快速幂是这样：

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

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

前缀和

简单来说

前缀和主要是减少了重复的运算，比如有一个问题，每一次处理需要得到 ∑a_i(i = m->n-1)，其中，n 为定值而 m 不定，那么常规操作是每一次处理都重新对索引 m->n-1 的数求和。但实际上，可以用一个数组来专门存储 m->n-1 的和（比如那个数组叫做 sum，那么 sum[m]则表示 ∑a_i(i = m->n-1)）。这样，预先构造好 sum 数组，每次处理只需要要直接访问 sum 数组就好（最大可将复杂度从 O(n²) 降到 O(n)）。

Show Me The Code

sum 数组的构造过程大概就是：

sum,sumNums = [0 for i in range(n)],0for i in range(n-1,-1,-1):    sumNums += a[i]    sum[i] = sumNums

后语

未完待续。😃

转载地址：http://mmbws.baihongyu.com/