js算法-查找斐波纳契数列中第N个数

所谓的斐波纳契数列是指前2个数是 0 和 1 ，第 i 个数是第 i-1 个数和第i-2 个数的和。大致可以描述为a(n) = a(n-1) + a(n-2) (a >=2)。类似于这样[1, 1, 2, 3, 5, 8, 13 ...]。  具体大家可以百度一下。下面我们来用js获取菲波那契数列的第N个数为多少：

1.递归  

var a = function(n) {
    if (n === 1 || n === 2) {
        return 1
    } else {
        return a(n - 1) + a(n - 2)
    }
}
console.time('a（44）')
console.log(a(44))
console.timeEnd('a（44）')

以上我们可以比较清晰的看出代码的思路，但是这种方法有一个致命的缺点：效率太差！不信你看：

701408733
VM381:10 a（44）: 5768.427734375ms

执行到第44个的时候，已经不能接受了，需要5s多。那我们再来改进一下  

2.闭包+缓存  

var b = (function() {
    var cache = {
        1: 1,
        2: 1
    }
    return function(n) {
        if (cache[n]) {
            return cache[n]
        } else {
            cache[n - 1] = b(n - 1)
            cache[n - 2] = b(n - 2)
            return cache[n - 1] + cache[n - 2]
        }
    }
})()

console.time('b（1200）')
console.log(b(1200))
console.timeEnd('b（1200）')

将每一步计算出来的值，保存到了缓存中。效率提升了许多：  

2.7269884455406272e+250
VM383:19 b（1200）: 0.630126953125ms

3.直接计算出该数列的值得数组，然后再从数组中取值 

var c = function(n) {
    var arr = [1, 1]
    if (n === 1 || n === 2) {
        return 1
    }
    for (var i = 2; i < n; i ++) {
        arr[i] = arr[i - 1] + arr[i - 2]
    }
    return arr[n - 1]
}

console.time('c（1200）')
console.log(c(1200))
console.timeEnd('c（1200）')

这样效率又进一步提高了不少：  

2.7269884455406272e+250
VM436:13 c（1200）: 0.36181640625ms

4.直接使用数学表达式  

那这样还有没有更快的方法呢？当然有！菲波那契数列是有数学表达式的。我们为何不直接使用数学表达式呢？

var d = function(n) {
    return (1/(Math.pow(5, 1/2))) * (Math.pow((1 + Math.pow(5, 1/2))/2, n) - Math.pow((1 - Math.pow(5, 1/2))/2, n))
}

console.time('d（1200）')
console.log(d(1200))
console.timeEnd('d（1200）')

效率如下：

2.7269884455406177e+250
VM428:7 d（1200）: 0.424072265625ms

本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！

链接: https://shenqiku.cn/article/FLY_1097