关闭

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

时间: 2018-09-19阅读: 1549标签: 算法

所谓的斐波纳契数列是指前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.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

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

关闭

JavaScript十大排序必修算法

冒泡排序通过相邻元素的比较和交换,使得每一趟循环都能找到未有序数组的最大值或最小值,双向冒泡普通的冒泡排序在一趟循环中只能找出一个最大值或最小值,双向冒泡则是多一轮循环既找出最大值也找出最小

JS 洗牌算法

最近的一个塔罗牌项目中,有一个洗牌的需求,其实也就是随机打乱数组,遂网上搜了下,再此做个整理…塔罗牌,举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9:

为什么我认为数据结构与算法对前端开发很重要?

一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:前端这边想要将数据转换一下其实也不难,因为要合并重复项

js实现1万的阶乘

但是这样就会存在问题,Js中最大的安全整数为2^53- 1,10000!结果溢出该范围,代码运行结果为Infinity,无法计算出正确的结果。那么如何才能计算大数据的阶乘呢?

js字典对象_js实现字典Dictionary类操作

字典(Dictionary)是一种以 键-值对 形式存储数据的数据结构 ,其实对于javascript来说,字典类(Dictionary)的基础是Array类,js中的Array既是一个数组,同时也是一个字典。字典(Dictionary)类的基础是 Array 类。同之前的我们所看到的数据结构一样,字典类也应该有添加、删除、清空等操作。

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

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

Js排列组合的实现

犹记得高中数学,组合表示C(m, n),意思为从集合m,选出n个数生成一项,总共有多少个项的可能?组合是无序的,排列是有序的。所以排列的项数量多于组合

JavaScript字符串压缩_js实现字符串压缩

设计一种方法,通过给重复字符计数来进行基本的字符串压缩。例如,字符串 aabcccccaaa 可压缩为 a2b1c5a3 。而如果压缩后的字符数不小于原始的字符数,则返回原始的字符串。 可以假设字符串仅包括a-z的字母

js二叉树的遍历算法

二叉树是非常重要的数据结构,其中一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称为度,二叉树每个节点的度只能是0,1,2中的一个,度为0的节点称为叶节点。

js求数组中的最大差值的方法总汇

有一个无序整型数组,如何求出这个数组中最大差值。(例如:无序数组1, 3, 63, 44最大差值是 63-1=62)。实现原理:遍历一次数组,找到最大值和最小值,返回差值

点击更多...

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