关于算法效率的一些思考
减少冗余计算
如果一个算法中包含了某些冗余的计算过程，那么一定有办法可以继续优化。
比如双重递归
#下面是一个求2的幂的运算
def powerOfTwo1 (n):
if n == 0:
return 1
else if n == 1:
return 2
else
return powerOfTwo1( n//2 )*powerOfTwo1( (n+1)//2 )
这里powerOfTwo(n//2)和powerOfTwo((n+1)//2) 两部分的计算是有冗余的，当n是偶数时，2个结果一样，但是却重复了计算；而当n是奇数时，powerOfTwo((n+1)//2) = 2 * powerOfTwo(n//2), 同样计算出现冗余，时间复杂度达到O(2^n)，所以可以进一步优化。
def powerOfTwo2 (n):
if n == 0:
res = 1
else
res = 2*powerOfTwo2(n-1)
return res
优化后时间复杂度为O(n)
加大计算粒度
当然上面的powerOfTwo2算法还不算太好，某种程度上来说里面还存在冗余，因为有太多重复的 乘2 操作了，如何进一步减少这些操作呢？那就是在运算过程中动态地改变计算粒度。
def powerOfTwo3 (n):
if n == 0:
return 1
table = [2]
res = 1
while(n):
if len(table) >= n:
res *= table[n-1]
n = 0
else:
table.append(2*table[-1])
res *= table[-1]
n -= len(table)
return res
这次powerOfTwo3会动态地改变每一次计算的粒度，从最小的2开始，之后可能为更大的4、8、16等。
比如计算2的13次方幂，运算过程为2 * 4 * 8 * 16 * 8， 即2 * 2^2 * 2^3 * 2^4 * 2^3
此时时间复杂度变为O(logN)
当然上面的指数n是通过减法衰减的( n -= len(table) ), 因此还能更快，比如使用除法来更快地衰减n，比如下面
#求k的n次方， powerOfTwo4(n) = power4(2,n)
def power4 (k, n):
if n == 0:
return 1
else:
if n % 2 == 0:
return power4( k*k, n//2 )
else:
return k * power4( k*k, n//2 )
这种方法每次运算基于的底数都不同，即新的运算粒度，因此需要保存新的底数，就像power4函数中的参数k，但是这点空间换来的效率提升是完全值得的。
这里之所以能加大计算粒度，是因为每次幂运算都是基于相同的底数，即2，因此相当于另一种形式的“冗余计算”，但是有时候在计算中也许不能进一步加大计算粒度，比如下面的阶乘计算：
#计算n!
def fac(n):
if n == 0:
return 1
else
return n*fac(n-1)
阶乘里每一次运算操作的对象都不同，因此不存在冗余，不能进一步加大粒度。
加大计算粒度的方法很多，具体多大的粒度才最好，这还要看需要处理的数据的规模。
减少乘除
有时候某个算法的粒度已经不小，而且操作过程也没有明显的冗余，这时候某些细微的运算过程或许还潜藏着冗余操作，可以从减少乘除运算的角度去进一步优化。
下面是一个求整数平凡根的程序，eg. intRoot(7) = 2
def increase( r, n ):
return r if (r+1)*(r+1) > n else r+1
def intRoot(n) :
if n == 0:
return 0
else:
return increase( intRoot( n // 4 ) * 2, n )
操作的参数n每次以4倍的速度衰减，貌似已经没有冗余。但是increase里的(r+1)*(r+1)性能消耗还是有点大，可以看看能否进一步优化，如下：
def intRootOptimize(n):
if n == 0:
return [0,0]
else:
preR, preR2 = intRootOptimize( n//4 )
incR2 = 4*preR2 + 4*preR + 1
if incR2 > n:
return [ 2*preR, 4*preR2 ]
else:
return [ 2*preR+1, incR2]
incR2 = 4*preR2 + 4*preR + 1 即前面的(2r+1)*(2r+1),这里的运算更适合编译器优化，可以优化为移位运算，效率提高许多。