本文算法使用python3实现
1.题目描述:
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。n<=39
时间限制:1s;空间限制:32768K2.思路描述:
实现斐波那契额数列主要有两种方法:
(1)递归法:自顶向下进行,当递归较深时,时间复杂度是很高的。 (2)迭代法:自底向上进行,从第0项开始计算,并将结果保存起来,最后返回第n项即可。该方法时间复杂度较低,但需要额外空间,相对于递归来说,是一种空间换时间的方法。 接下来我们将分别对两种方法进行实现,并比较两者的时间消耗。3.程序代码:
递归法
class Solution: def Fibonacci(self, n): '''递归法''' if n in [0,1]: return n return self.Fibonacci(n-2)+self.Fibonacci(n-1)
所需时间:
迭代法class Solution: def Fibonacci(self, n): '''迭代法''' FibList = [] # 将前n项保存在数组中 for i in range(n+1): if i in [0,1]: FibList.append(i) continue FibList.append(FibList[-2]+FibList[-1]) return FibList[-1]
所需时间: