PS：以下代码是以Python3来实现的
一、递归
时间复杂度：O(2n)
空间复杂度：O(1)
（不能使用这种代码，但是递归确实又是基本，因为递归是最简单的，所以还是知道有这么回事就行）
def fib_recursion(n: int) -> int:
if n <= 0:
return 0
if n == 1 or n == 2:
return 1
else:
return fib_recursion(n-2) + fib_recursion(n-1)
二、迭代(或动态规划)
时间复杂度：O(n)
空间复杂度：O(1)
def fib_iteration(n: int) -> int:
if n <= 0:
return 0
a, b = 0, 1
for _ in range(n):
a, b = b, a+b
return a
三、斐波那契矩阵
时间复杂度：O(log2n)
空间复杂度：O(1)
根据以下斐波那契矩阵公式，即可求出相应第n项的值：
同时：
)
)
所以：利用二分法实现快速幂，就可以达到O(log2n)，只不过这里还需要自己去实现2×2矩阵的乘法运算，其他都类似
（PS：如果使用numpy的矩阵，可能计算会快一点(我没去尝试，有兴趣的大佬可以去试试)，
但是毕竟numpy不是Python的内置包，所以笔试或面试像下面这样写都可以了，主要是掌握核心的快速幂的二分思想）
from typing import List
# 定义2×2矩阵的乘法运算
def matrix_mul(a: List[List[int]], b: List[List[int]]) -> int:
c = [[0, 0], [0, 0]]
c[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0]
c[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1]
c[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0]
c[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1]
return c
def fib_matrix(n: int) -> int:
if n <= 1:
return max(n, 0)
res = [[1, 0], [0, 1]] # 单位矩阵
base = [[1, 1], [1, 0]] # 斐波那契的基础矩阵
# 快速幂
while n:
if n & 1:
res = matrix_mul(res, base)
base = matrix_mul(base, base)
n >>= 1
return res[0][1]
四、斐波那契通项公式
时间复杂度：O(1)
空间复杂度：O(1)
知道公式，就是转换成代码，没什么技术含量
斐波那契数列的通项公式为：
%5E%7Bn%7D%20-%20(%5Cfrac%7B1-%5Csqrt%7B5%7D%7D%7B2%7D)%5E%7Bn%7D))
注意：在Python3里，当n较大时(大概1500左右)，下面这个就会抛出Overflow异常
from math import sqrt
def fib_formula(n: int) -> int:
return int(1/sqrt(5) * (pow((1+sqrt(5))/2, n) - pow((1-sqrt(5))/2, n)))
#Python##笔试题目#
