斐波纳挈数列 DAY1

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

n<=39

1.算法复杂度为2的n次方

# -*- coding:utf-8 -*- # 0 1 1 2 3 5 8 13 # n=k(n>1),f(k)=f(k-1)+f(k-2) # n=1 f(1)=1 # n=0 f(1)=0 class Solution: def Fibonacci(self, n): # write code here # 递归：复杂度2的n次方 if n==0 : return 0 if n==1 : return 1 if n>1 : num= self.Fibonacci(n-1)+self.Fibonacci(n-2) return num return None

2.算法复杂度为n

 

# -*- coding:utf-8 -*- # 0 1 1 2 3 5 8 13 # n=k(n>1),f(k)=f(k-1)+f(k-2) # n=1 f(1)=1 # n=0 f(1)=0 class Solution: def Fibonacci(self, n): # write code here ''' # 递归：复杂度2的n次方 if n==0 : return 0 if n==1 : return 1 a=0 b=1 for i in range(0,n-1): c = a + b a = b b = c return c