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

更新日期: 2018-09-19阅读量: 2068标签: 算法

所谓的斐波纳契数列是指前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


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: https://www.fly63.com/article/detial/1097

数据结构与算法之绪论

什么是数据结构?简单来说可以解释为:程序设计=数据结构+算法;主要是用来研究数据结构的关系,数据元素之间存在的一种或多种特定关系的集合;

React 中 Virtual DOM 与 Diffing 算法的关系

Virtual DOM 是一种编程理念。UI 信息被特定语言描述并保存到内存中,再通过特定的库,例如 ReactDOM 与真实的 DOM 同步信息。这一过程成为 协调 (Reconciliation)。上述只是 协调算法

JS数据结构与算法_链表

链表更加像是数组。链表和数组都是用于存储有序元素的集合,但有几点大不相同,链表的实现不像之前介绍的栈和队列一般依赖于数组(至少我们目前是这样实现的),它必须自己构建类并组织逻辑实现。我们先创建一个Node类

js背包问题算法_JavaScript 背包问题详解

打算好好学一下算法,先拿背包问题入手。最开始的01背包耗时最多,以前只会枚举(就是普通的for循环,暴力地一步步遍历下去),递归与二分,而动态规划所讲的状态表与状态迁移方程为我打开一扇大门。

js实现合并两个有序数组

给定两个有序整数数组arr1和arr2,将 arr2和arr1进行合并为一个单调非递减的数组,并将其输出。方法一利用循环、方法二直接使用数组的sort方法。

js实现分解质因数

定义一个数组,用来存放因数; 定义数组里面数的位置的起始值0;定义分解质因数的函数;如果被分解的数为1、2、3,则直接存入数组,并返回结果

js生成32位uuid算法总汇_js 如何生成uuid?

GUID是一种由算法生成的二进制长度为128位的数字标识符。GUID 的格式为“xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx”,其中的 x 是 0-9 或 a-f 范围内的一个32位十六进制数。在理想情况下,任何计算机和计算机集群都不会生成两个相同的GUID。

js生成guid

全局唯一标识符(GUID,Globally Unique Identifier)也称作 UUID(Universally Unique IDentifier) 。GUID是一种由算法生成的二进制长度为128位的数字标识符。GUID 的格式为“xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx”

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

原生js数值开根算法

理论上来讲,开根后的值为x,那么x^2=n,即可以将其转换为数学问题,令y=x^2-n,那么只需要求方程与x轴正方向的焦点就可以得出想要的结果,我们作x=a与方程交于(a^2-n),求得他的切线与x轴的交点

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!