斐波那契数列的多种解法

这里斐波那契数列从0开始，题目以leetcode 509. 斐波那契数 (opens new window)为准

递归算法时间复杂度的计算

递归时间复杂度 = 递归次数 * 每次递归的操作次数

简单粗暴递归

var fib = function(n) {
    if(n <= 1) return n
    return fib(n-1) + fib(n-2)
};

缺点很明显：

1. 很多重复的计算没有利用起来。

2. 时间复杂度分析：可以看看这篇回答 (opens new window)，网上大部分答案都是O(2^n)，其实更确切来说应该是二分之一加根号五的平方，实际上是比O(2^n)小一些

需要注意的是，这种计算方法的递归二叉树的叶子节点数量就是fib(n)，因为相当于把fib(n)个1进行相加。

尾递归优化

尾递归就是在函数末尾调用函数。

var fib = function(n, a = 0, b = 1) {
    if(n === 0) return 0
    if(n === 1) return b
    return fib(n-1, b, a + b)
};

时间复杂度应该是O(n),调用自身n次

使用数组迭代

也算是最简单的动态规划吧

var fib = function(n) {
    const arr = Array(n + 1).fill(0)
    arr[1] = 1
    for(let i = 2; i <= n; i++){
        arr[i] = arr[i-1] + arr[i-2]
    }
    return arr[n]
};

时间复杂度为O(n)

由于额外使用了一个数组，空间复杂度为O(n)

使用两个变量迭代

var fib = function(n) {
    if(n <= 1) return n
    let p1 = 0, p2 = 1
    for(let i = 2; i <= n; i++){
        const temp = p2
        p2 = p1 + temp
        p1 = temp
    }
    return p2
};

时间复杂度O(n)