计算运行时间
import time
def cal_time(func):
def wrapper(*args,**kwargs):
t1 = time.time()
result = func(*args,**kwargs)
t2 = time.time()
print("%s running time: %s secs." % (func.__name__,t2 - t1))
return result
return wrapper
斐波那契三种写法
斐波那契数列 1 1 2 3 5 8 ... F(n) = F(n-1)+F(n-2) F(0)=1 F(1)=1,时间复杂度O(2 ^ n)
- 方法1,使用递归,时间复杂度有点复杂先不研究..
def fibnacci(n):
if n == 0 or n == 1:
return 1
else:
return fibnacci(n-1) + fibnacci(n-2)
#由于使用了递归,需求套个函数才能计算运行时间,否则运行时间也会不断递归
@cal_time
def fib1(n):
return fibnacci(n)
print(fib1(10))
- 方法2,使用列表存储每次的结果,增加了空间复杂度
#时间复杂度O(n),空间复杂度O(n)
@cal_time
def fib2(n):
li = [1,1] #设置0、1下标的初始值
for i in range(2,n+1):
li.append(li[-1] + li[-2])
return li[n]
print(fib2(10))
- 方法3最优,使用变量只存储最近的两次结果,空间复杂度只有O(1)
#时间复杂度O(n),只有几个变量,所以空间复杂度O(1)
@cal_time
def fib3(n):
a = 1
b = 1
c = 1
for i in range(2,n+1):
c = a + b
a = b
b = c
return c
print(fib3(10))
网友评论