【JS 小短文】{{BANNED}}版斐波那契

sihai 发布于2019-08-20 12:23 / 2657人阅读

摘要：转载自我的博客效率呢斐波那契数列大家应该再熟悉不过了，平时面试也经常会被问到，然而不知道大家有没有考虑过它的效率呢普通版我们一般给出的代码应该是这样的这段代码逻辑完全没问题，但是如果你稍测试一下可能就会发现问题了，比如可以试一下，这时你

转载自我的博客

效率呢？

斐波那契数列大家应该再熟悉不过了，平时面试也经常会被问到，然而不知道大家有没有考虑过它的效率呢？

普通版

我们一般给出的代码应该是这样的：

function fibonacci(n) {
    if(n==0 || n == 1)
        return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

这段代码逻辑完全没问题，但是如果你稍测试一下可能就会发现问题了，比如可以试一下 fibonacci(70)，这时你可能吃个饭回来它还没执行完。

{{BANNED}}版

之所以叫它“{{BANNED}}版”，是因为在fibonacci(1000)以下基本可以在 5 毫秒之内完成，效率提升了 Infinity 倍，然而为什么差距这么大？我们先看个图：

这是n = 5的时候的计算过程，显而易见，它包含了很多次重复的计算，优化它也很简单，我们只需要加个缓存（这里用到了闭包），代码如下：

var fibonacci = (function() {
  // 这里我用了 Map，用普通对象也是可以的
  var cache = new Map();
   return function(n){
       if(n == 0 || n == 1){
       cache.set(n,n);
       return n;
      }
      var v1 = cache.get(n-1) ? cache.get(n-1):fibonacci(n-1);
      var v2 = cache.get(n-2) ? cache.get(n-2):fibonacci(n-2);
      var nVal = v1 + v2;
      cache.set(n, nVal);
      return nVal;
   }
})()

云服务器 GPU云服务器波那契数列解斐波短文 js小技能

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/80954.html

增强版斐波纳契函数Tribonacci

摘要：很好地遇到了斐波那契更大的兄弟，。它基本上像斐波纳契一样，但是将序列的最后个而不是个数相加以生成下一个。入参的数组始终包含个数字将始终为非负数，然后返回一个空数组。同时需要注意的的情况。很好地遇到了斐波那契更大的兄弟，AKA Tribonacci。它基本上像斐波纳契一样，但是将序列的最后3个（而不是2个）数相加以生成下一个。所以，如果我们要以开始[1, 1, 1]输入开始我们...

JellyBool 2019-08-16 16:22 评论0 收藏0
js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0
斐波那契数列求和的js方案以及优化

摘要：在上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。动态规划解决方案斐波那契数列求和除了可以用递归的方法解决，还可以用动态规划的方法解决。在codewars上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。题目 function fibonacci(n) { if(n==0 || n == 1) r...

xinhaip 2019-08-20 11:35 评论0 收藏0
太原面经分享：如何用js实现返回斐波那契数列的第n个值的函数

摘要：那其实这个问题还可以换个问法实现一个函数，输入一个数字能返回斐波那契数列的第个值。文章预告更多的前端面试分享我都会第一时间更新在我的公众号闰土大叔里面，欢迎关注面试攒经验，lets go！值此高考来临之际，闲不住的我又双叒叕出发去面试攒经验了，去了公司交待一番流程后，面试官甩给了我一张A4纸，上面写着一道js算法笔试题（一开始我并不知道这是在考察js算法），上面写着1、1、2、3、...

Galence 2019-08-26 12:01 评论0 收藏0
js实现斐波那契数列

摘要：实现斐波那契数列斐波那契数列最大数斐波那契数列由和开始之后的斐波那契数列系数就由之前的两数相加。换个写法，用箭头函数最大数斐波那契数列由和开始 js实现斐波那契数列 // 斐波那契数列 let max=10000; // 最大数 let arr=[0,1]; // 斐波那契数列由 0 和 1 开始 // 之后的斐波那契数列系数就由之前的两数相加。 ...

notebin 2019-08-23 15:42 评论0 收藏0