关闭

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

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

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

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

Js实现插入排序

插入排序是一种非常简单的算法,最适合大部分已经被排好序的数据。在开始之前,通过可视化演示算法如何运作一个好主意。你可以参考前面的动画来了解插入排序的工作原理。

JS常见简单算法排序

我们面试中经常会遇到排序算法问题,我整理了冒泡排序、选择排序、插入插排等常见简单排序方法。希望此文想对了解排序的前端同学有所帮助。为了简单高效演示算法的实现思路,我先封装一个构造函数

用js在控制台打印九九乘法表

不管是打印什么样三角形九九乘法表,我们都应该找到有规律的地方,比如第一列的数字是什么规律,第一行的数字是什么规律,只要找到了共性,九九乘法表就很简单

js实现链表_javascript中的链表结构

很多编程语言中数组的长度是固定的,就是定义数组的时候需要定义数组的长度,所以当数组已经被数据填满的时候,需要再加入新的元素就很困难。只能说在部分变成语言中会有这种情况,在javascript中和php中数组的长度是可以任意增加的。avascript中有一个很方便的方法splice()方法很方便的就可以添加或删除元素。

JS排序算法:记数排序

计数排序是一个非基于比较的[排序算法],该算法于1954年由 Harold H. Seward 提出。 它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围), 快于任何比较排序算法。

Js队列和双端队列

最新添加的元素必须排在队列的末尾。在生活中也有队列的应用,比如我们在售票处排队等票,队头的人先拿到票,就走了,而新来的人,就必须排在队伟文明排队。

js常见排序算法实现:冒泡排序,快速排序

冒泡排序原理:对数组进行遍历,根据相邻两个元素大小进行交换,每一次遍历都将最小值推至最前方,然后对剩下的值再次进行比较;快速排序原理:从数组中取一个基准值,将剩下的值与基准值比较

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

js实现斐波那契数列的几种方式

斐波那契指的是这样一个数列:1、1、2、3、5、8、13、21、34......在数学上,斐波纳契数列以如下被以递归的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*);随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..…

js二分查找算法

二分查找高效的前提是数据结构是有序的。就好比猜1~100之间的数,先猜50,如果太大了就猜25,如果太小了就猜75.每一次都猜最大值和最小值的中间点.

点击更多...

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