计算运行时间

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))