递归计算斐波那契数列：

class Solution:
    def Fibonacci(self , n ):
            if n <= 2:
                return 1
            else:
                return self.Fibonacci(n-1)+self.Fibonacci(n-2)

当计算斐波那契数列时，使用递归的方式是比较简洁的，但是效率不高，尤其是当计算较大的斐波那契数时，递归会导致重复计算，造成性能下降。可能出现运行超时现象。

  • 时间复杂度：O(2^n)。递归版本的斐波那契数列实现会重复计算许多相同的子问题，导致指数级别的时间复杂度。
  • 空间复杂度：O(n)。递归版本需要消耗系统栈空间，递归深度达到 n，因此空间复杂度随着输入规模线性增长。

更高效的方法是使用迭代或动态规划。

迭代版本：

#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n ):
            if n < 2:
                return n
            else:
                fa = 0   #f0=0
                fb = 1   #f1=1
                for i in range(2,n+1):
                    fa,fb = fb, fa+fb
                return fb

在这个改进版本中，我们使用两个变量 fa 和 fb 来迭代计算斐波那契数列。初始时，fa 表示第 0 项，fb 表示第 1 项。然后，循环从第 2 项开始，利用迭代更新 fa 和 fb 的值，直到计算到第 n 项。

这种迭代的方式避免了递归带来的重复计算，因此在效率上更高。

  • 时间复杂度：O(n)。迭代版本使用循环从第 2 项开始计算斐波那契数值，总共需要进行 n-1 次迭代。
  • 空间复杂度：O(1)。迭代版本只使用了常数级别的额外空间，无论输入规模是多少，所需的额外空间都保持不变。

使用动态规划的版本可以进一步优化斐波那契数列的计算效率。动态规划将问题划分为子问题，并利用子问题的解构建更大规模问题的解。

动态规划版本：

class Solution:
    def Fibonacci(self , n ):
            #首先处理边界情况
            if n < 2:
                return n

            #用于存储计算过程中的斐波那契数值
            f = [0]* (n+1)

            #初始值
            f[0] = 0
            f[1] = 1

            #递推计算斐波那契数列
            for i in range(2,n+1):
                f[i] = f[i-1] + f[i-2]
            return f[n]

我们使用一个数组  f 来存储计算过程中的斐波那契数值。初始时，我们将数组中的前两个元素设置为 0 和 1，分别代表第 0 项和第 1 项。

然后，我们通过一个循环从第 2 项开始，使用递推关系f[i] = f[i - 1] + f[i - 2] 计算每一项的斐波那契数值。最终，f[n]  即为第 n 项的斐波那契数值。

注意： f= [0] * (n + 1) 是一个将列表 f 初始化为长度为 n+1 的列表，并且列表中的每个元素都初始化为 0 的操作。

在斐波那契数列的动态规划解法中，我们使用列表 f 来存储计算过程中的斐波那契数值。由于斐波那契数列的索引是从 0 开始的，因此我们需要初始化列表 f 的长度为 n+1，这样可以确保列表中的索引从 0 到 n 都有对应的位置。

这里使用乘法的方式，将 0 乘以 (n + 1) 来创建一个含有 n+1 个元素的列表，并将每个元素初始化为 0。例如，当 n 的值为 5 时，f  列表的初始化结果为 [0, 0, 0, 0, 0, 0]。

  • 时间复杂度：O(n)。动态规划版本利用了子问题之间的重叠性质，通过迭代计算并存储中间结果，总共需要进行 n-1 次迭代。
  • 空间复杂度：O(n)。动态规划版本使用了一个长度为 n+1 的列表 f 来存储斐波那契数值，占用了线性额外空间。