求计算算法的复杂度 （Python写的逻辑）
# computational complexity
# a)
i=0
while(i<n):
i=i+1
# b)
k=0
for i in range(n):
for j in range(n/2):
k=k+1
# c)
i=1
while(i<n):
i=2*i
# d)
def func(i):
if(i>1):
func(i/2)
# e)
map(func,range(n))
注释：func为楼上#g的function
# f)
def func2(i):
if(i>2):
return func2(i-1) + func2(i-2)
else:
return 1
func2(n)
# g)
def func3(i):
if(i>2):
f=[1,1,2]
for j in range(i-3):
f[0]=f[1]
f[1]=f[2]
f[2]=f[0]+f[1]
return f[2]
else:
return 1
func3(n)
(b) 算法复杂度为O(n²)，实际上算法复杂度为nxn/2 = n²/2，因为有for循环的嵌套
(c) 算法复杂度为O(n)，因为只有while循环，尽管里面i=ix2，但是这是常数级操作
(d) 算法复杂度为O(log i)，这是对数级操作，每次i除以2，所以是log(i)base(2)
(e) 算法复杂度为O(n log n)
(f) 算法复杂度为O(2^i)，这是一个递归算法，为指数级
(g) 算法复杂度为O(n 2^n)，这是一个交换数据的算法，是一个递归+一个for 循环追问
c) i=i*2 是常数级操作 但是直接影响到与<n的比较 （条件），为何还是o(n)呢
d,f) 我觉得是 O(math.sqrt(n))吧 每次嵌套我搞不清了
g) 这里交换数据只和 for j in range(i-3)有关吧，这个for循环执行次数应该只与n有关吧（3*（n-3)) 我觉得应该是1+1+(n-3)*3+1=3n-6即 O(N)
有没有好的教程参考贴，推荐下。谢谢了。
(c) 当n越大的时候，要操作的次数也越多，所以跟n有关，是O(n)
(d,f) 这个实际上牵涉到了一个递归树，所以是对数级的，log n，这相当于一个二分查找
(g) 哦，这一个没看清楚，以为用到了递归，不好意思，是O(n)
我推荐你看《算法导论》，砖头书，要变成大神还是要下苦工啊...编程之路，路漫漫其修远兮，吾将上下而求索。
兄台对楼下答案有无反驳？我觉得C）楼下较有道理。f)的话对数级应该是没有问题的吧
追答(c) 我没有反驳，楼下说的是对的，我确实没有考虑到i的增长率问题，有欠考虑，真是不好意思。
(f)的话，楼下说的也没错，但是用O表示的话实际上就相当于O(2^n)，所以要看您到底是要怎么表示，是对数级没错。
#b 一共要做n^2/2次加法，算法复杂度为O(n^2)。
#c 要求一个k，满足2^k>=n ，算法复杂度为O(log(n))
#d 注意到这个函数做的事跟#c的函数恰好相反，算法复杂度相同，也是O(log(n))
#e 因为已算出#g每次做3(n-3)次加法，那么i从1到n，一共做2/3*(n^2-5n+6)次加法，所以复杂度为O(n^2)。
#f 这个函数可以写成公式T(n)=T(n-2)+T(n-1)，这个递归式跟黄金分割有关系，解这个递归式，可以知道 T(n) = O((√5-1/2)^n)
#g 函数调用一共做3(n-3)次加法，所以复杂度为O(n)
PenitentSin 这位兄台的#c 算的不对啦，#g也不对。还有#f，这个虽然是递归，但不是递归就等于指数级的复杂度，要解递归方程才能断定的。
关于算法复杂度，《算法导论》一书中第四章有一个主定理，记住这个定理之后，这些问题就小case了（除了复杂递归之外）。追问
讲解详细 较优质的答案啊。期待楼上的讨论，看来是需要找本算法书好好看看了，毕竟不是科班出身。
追答PenitentSin 对#f的理解是不对的，不是说指数的复杂度都是O(2^n)，底数不同的时候，复杂度不同的，O(1.5^n), O(2^n), O(3^n) 这些结果是不同的复杂度。对数因为有换底公式（高中数学的内容），所以可以认为O(log(n)), O(log2(n)) 的时间复杂度是一样的，大O表示法就是说在乘积相差一个常数的情况下能有相同的无穷大的阶，但是指数函数没有这样的性质，所以不能认为是等同的。
本回答被提问者采纳