1. 常规递归斐波那契数列解法

时间复杂度 O(n^2) ,空间O(1)

def foo(d):
    if d == 1 or d == 2:
        return 1
    return foo(d-2)+foo(d-1)

foo(10)

2. 空间换取时间

时间复杂度O(n),空间复杂度O(n)

import numpy as np
# 使用空间换取时间
def fib(n):
    tmp = np.zeros(n) 类似于数列保存之前的数
    tmp[0] = 1
    tmp[1] = 1
    for i in range(2,n):
        tmp[i] = tmp[i-2]+tmp[i-1]
    return tmp[n-1]
fib(7)

3. 优化空间复杂度

时间复杂度O(n),空间复杂度O(1)

def fib(n):
    # 优化空间复杂度为O(1) 时间复杂度O(n)
    a = b = 1
    for i in range(2,n):
        c = a+b
        a = b
        b = c
    return c
fib(7)

4. 优化时间复杂度为O(1)

时间复杂度O(logN),空间复杂度O(1)

f(n) = closed-form solution 一般翻译为闭合解/解析解。这一般是相对于数值解而言的。
套公式：为O（1）的时间复杂度
思考：公式由来？
提示：转化为矩阵的连乘的形式，矩阵连乘可以简化
参考推导过程：https://blog.csdn.net/flyfish1986/article/details/48014523

import numpy
def Fibonacci_Matrix_tool(n):
    Matrix = numpy.matrix("1 1;1 0")
    # 返回的是matrix类型
    return pow(Matrix, n)

def Fibonacci_Matrix(n):
    result_list = []
    for i in range(0, n):
        result_list.append(numpy.array(Fibonacci_Matrix_tool(i))[0][0])
    return result_list
# 调用
if __name__ == '__main__':
    a = Fibonacci_Matrix(10)
    print(a)