斐波那契数列简介

斐波那契数列是一种常见的数列，其满足下面两个条件

F0=F1=1

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Fn=Fn-1+Fn-2


斐波那契数列求解

使用递归

def fib1(n):
    if n < 2:
        return 1
    return fib1(n-1) + fib1(n-2)


不适用递归

def fib2(n):
    f1 = f2 = 1
    for i in range(1, n):
        f1, f2 = f2, f1+f2
    return f2


两种算法比较

使用递归的算法时间O(1.618^n)
不适用递归的算法O(n)

import time


# 使用递归
def fib1(n):
    if n < 2:
        return 1
    return fib1(n-1) + fib1(n-2)


# 不使用递归
def fib2(n):
    f1 = f2 = 1
    for i in range(1, n):
        f1, f2 = f2, f1+f2
    return f2


start_time = time.time()
print('fib1:', fib1(40))
end_time = time.time()
print('fib1:', end_time-start_time)


start_time = time.time()
print('fib2:', fib2(40))
end_time = time.time()
print('fib2:', end_time-start_time)



运行结果

fib1: 165580141
fib1: 34.63041615486145
fib2: 165580141
fib2: 0.0
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄