斐波那契数列即
1,1,2,...,f(n)=f(n-1) + f(n-2)
第n项等于第（n-1）项与第（n-2）项之和。
关于斐波那契数列的实现，最简单的一种，大家都会想到：
def fib1(n):if n==0 or n==1:return 1else:return fib1(n-1) + fib1(n-2) print(fib1(n)) 123456
但是这种方法的时间复杂度特别高，为O(2^n)，一般在计算到n=40以上就很慢了。原因是代码执行时进行了很多重复计算。
所以，为了提高代码效率，可以使用如下方法：
def fib2(n):li=[1,1]for i in range(2,n+1):li.append(li[-1]+li[-2]) #最后一项，加上倒数第二项return li[n] print(fib2(n)) 123456
计算快很多。时间复杂度为O(n)。
还有一种方法，是时间复杂度与fib2相同，但是占用的空间较小：
def fib3(n):a=1b=1c=1for i in range(2,n+1):c=a+ba=bb=creturn c print(fib3(n)) 12345678910
