Introduction

斐波拉契的启发：

方法一 ： 递归做法 这个算法的时间复杂度有着跟Fibonacci类似的递推方程：T(n) = T(n - 1) + T(n - 2) + O(1)，很容易得到T(n) = O(1.618 ^ n)（1.618就是黄金分割, 空间复杂度取决于递归的深度，显然是O(n)。

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

方法二： 循环方法：

def fibonacci(n):
    if n== 0 or n == 1:
        return n
    x , y, z = 0, 1, 0
    for i in range(2, n + 1):
        z = x + y
        x = y
        y = z
    return z

方法三：矩阵法，O(logn)