面试题10- I. 斐波那契数列(3种复杂度)

发表于 | 分类于

leetcode链接

解析

结果

方式 耗时 时间复杂度 空间复杂度
直接递归 7997 O(n^2) O(1)
备忘录 0 O(n) O(n)
动态规划 0 O(n) O(1)

最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var fib = function(n) {
    //0,1,2,3,5,8,13
    if(n<2){
        return n;
    }
    let prev0 = 0;
    let prev1 = 1;
    let res = 0;
    for(let i = 2;i<=n;i++){
        res = (prev0 + prev1) %(1e9+7);
        prev0 = prev1;
        prev1 = res;
    }
    return res;
};

次优

1
2
3
4
5
6
7
8
9
10
11
12
let memoize = new Map();
var fib = function(n) {
    if(memoize.has(n)){
        return memoize.get(n);
    }
    if(n<2){
        return n;
    }
    let re = fib(n-1) + fib(n-2);;
    memoize.set(n,re);
    return re;
};

最差

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