> For the complete documentation index, see [llms.txt](https://liuxue2010.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuxue2010.gitbook.io/data-structure-and-algorithms/master.md).

# 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)