leetcdoe剑指 Offer 10- I. 斐波那契数列

[2018212632]

leetcdoe剑指 Offer 10- I. 斐波那契数列

题目链接

• 剑指 Offer 10- I. 斐波那契数列

思路

1. 傻递归，根据Fibonacci数列的规律，f(n) = f(n-1) + f(n-2).time:O(n^2) space:O(n)
2. 循环，从正向模拟整个递归过程，这样可以优化时间复杂度，通过公式发现只有三个变量使用，可以通过滑动的方式优化空间复杂度。time:O(n) space:O(1)

// 循环的方式
var fib = function(n) {
    if(n==0) return 0
    if(n==1) return 1

    // loop
    let fn1 = 0
    let fn2 = 1
    let fn3 
    for(let i=2; i<=n; i++) {
        fn3 = (fn1 + fn2) % 1000000007
        fn1 = fn2
        fn2 = fn3
    }
    return fn2 
};

总结

正常的傻递归时间复杂度通常是O(2^n)，因为有很多重复计算的结点，因此可以通过记忆化优化，通过另外的数组存在已经算过的结点，如果发现计算了直接使用。大多数递归都可以都过自顶向上的循环来改写。