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

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

所谓的斐波纳契数列是指前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生成32位uuid算法总汇_js 如何生成uuid?

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

一些常用的语音特征提取算法

语言是一种复杂的自然习得的人类运动能力。成人的特点是通过大约100块肌肉的协调运动,每秒发出14种不同的声音。说话人识别是指软件或硬件接收语音信号,识别语音信号中出现的说话人,然后识别说话人的能力

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

js多叉树结构的数据,parent表示法转成children表示法

要求是将这个数组转成一个children表示法的对象,即从根节点开始,每个节点存有其子节点数组。转化效果如下(节点必须有个唯一标识符,以下id就是,并且转化前后其他属性保持不变,这里为了显示简洁没有加入其他属性。

前端Js排序算法:冒泡排序、 选择排序、快速排序

典型的排序方法,命名来自鱼呼吸时吹出的气泡,上层的气泡总是最大的。选择排序:顾名思义,每次都选择最小的,然后交换位置,快速排序思路:二分法,先找一个基数

Js全排列的六种算法具体实现

六种算法有些是对位置进行排列,例如回溯、排序等,因为这样可以适应各种类型的元素,而非要求待排列元素一定是数字或字母等

JS 洗牌算法

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

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

js实现统计一个字符串中出现最多的字母的方法总汇

给出一个字符串,统计出现次数最多的字母。方法一为 String.prototype.charAt:先遍历字符串中所有字母,统计字母以及对应显示的次数,最后是进行比较获取次数最大的字母。方法二 String.prototype.split:逻辑和方法一相同,只不过是通过 split 直接把字符串先拆成数组。

JS排序算法:记数排序

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

点击更多...

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