2012年5月25日星期五

flip遍历

问题
遍历长度为n的所有可能的0-1向量(N=2^n个),使得相邻输出的两个向量可以通过某一个下标取反得到。

算法1
O(N)时间,O(n)空间
n=4
l=[0]*n
def f(n):
if n<=0:return
n-=1
f(n)
l[n]=1-l[n]
print l
f(n)
f(4)
足够简洁,注意到递归的函数栈深度为n,所以空间复杂度为O(n)

算法2
O(N)时间,O(1)空间
n=4
l=[0]*n
print l
N=pow(2,n)
for step in xrange(1,N):
for p in xrange(1,n+1):
if step%pow(2,p)==pow(2,p-1):
l[p-1]=1-l[p-1]
print l
break
虽然两重循环,看似时间复杂度为O(nN),其实有内层循环有1/2的概率第一次if就break了,有1/4的概率第2次就break了,。。。有1/2^k的概率第k次就break了。
而级数sum{k/2^k}收敛,有上界,上界与n无关。故均摊内层循环时间为O(1),总时间就是O(N)了。

没有评论: