• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

fib

admin

11月 28, 2021

空间复杂度

  • 如果代码开了数组,则为数组长度
  • 如果有递归,则为递归深度
  • 如果有数组有递归,取最大值

递归:

def fib(n):
    """ 递归:时间复杂度O(2**n),空间复杂度O(N),树的高度"""
    if n < 3:
        return 1
    else:
        return  fib(n - 1) + fib(n - 2)

优化时间复杂度后写法:

def fib2(n):
    """ 循环:时间复杂度O(N),空间复杂度O(1)"""
    a,b =0,1
    for x in  range(n):
        a,b = b,a+b
    return b

def fib_while(n):
    """ 循环:T=O(N),S=O(1)"""
    a,b=0,1
    i=1
    while i<=n :
         print(b,end=" ")
         i =i+1
         a,b =b,a+b
if __name__ == '__main__':

for i in range(0,15):
print(fib2(i),end=',')
print(" =============")

fib_while(15)

结果如下:

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,
=============
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
Process finished with exit code 0

  

总结:

最坏:时间复杂度O(2^n),空间复杂度O(N)

最好:时间复杂度O(N),空间复杂度O(1)

 

发表回复

您的电子邮箱地址不会被公开。