斐波那契数列求和的js方案以及优化

xinhaip 发布于2019-08-20 11:35 / 1540人阅读

摘要：在上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。动态规划解决方案斐波那契数列求和除了可以用递归的方法解决，还可以用动态规划的方法解决。

在codewars上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。

题目

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

以上函数使用递归的方式进行斐波那契数列求和，但效率十分低，很多值会重复求值。题目要求使用 memoization方案进行优化。

My Solution

memoization方案在《JavaScript模式》和《JavaScript设计模式》都有提到。memoization是一种将函数执行结果用变量缓存起来的方法。当函数进行计算之前，先看缓存对象中是否有次计算结果，如果有，就直接从缓存对象中获取结果；如果没有，就进行计算，并将结果保存到缓存对象中。

let fibonacci = (function() {
  let memory = []
  return function(n) {
      if(memory[n] !== undefined) {
        return memory[n]
    }
    return memory[n] = (n === 0 || n === 1) ? n : fibonacci(n-1) + fibonacci(n-2)
  }
})()

使用闭包实现的memoization函数。测试通过之后，突然我有一个小疑问，如果将memory的类型由数组换成对象，它的运算效率会有什么变化？于是，我将memory的类型换成了对象，并写了一个函数测试两种数据类型的运算效率。

function speed(n) {
    let start = performance.now()
    fibonacci(n)
    let end = performance.now()
    console.log(end - start)
}

所有测试只在Chrome控制台测试,并且测试次数不多，结果不严谨，请多多包涵。

memory类型为数组时（单位：毫秒）：

speed(500)      // 0.8150000050663948
speed(5000)     // 3.1799999997019768
speed(7500)     // 4.234999991953373
speed(10000)    // 8.390000000596046

memory类型为对象时（单位：毫秒）：

speed(500)      // 0.32499999552965164
speed(5000)     // 1.6499999985098839
speed(7500)     // 2.485000006854534
speed(10000)    // 2.9999999925494194

虽然测试过程不严谨，但还是可以说明一点问题的。memory类型为对象是明显比类型为数组时，运算速度快很多。~~至于为什么对象操作比数组操作的速度快，请原谅我水平有限，暂时答不上来。（先挖好坑，以后回来填坑，逃）~~现在回来填坑，例如我们调用fibonacci(100)，这时候，fibonacci函数在第一次计算的时候会设置memory[100]=xxx，此时数组长度为101，而前面100项会初始化为undefined。正因为如此，memory的类型为数组的时候比类型是对象的时候慢。（这里药感谢hsfzxjy的提醒）

Best Solution

别人的解决方案给了我灵感，让我想出了一个缓存效率高很多的方案。

var fibonacci = (function () {
  var memory = {}
  return function(n) {
    if(n==0 || n == 1) {
      return n
    }
    if(memory[n-2] === undefined) {
      memory[n-2] = fibonacci(n-2)
    }
    if(memory[n-1] === undefined) {
      memory[n-1] = fibonacci(n-1)
    }
    return memory[n] = memory[n-1] + memory[n-2]
  }
})()

测试结果就不放了（因为我发现在Chrome控制台中运行测试代码时，输出结果不稳定）。不过，这里的缓存效率的确是提高了，前面的方案，一次计算最多缓存一个结果，而这个方案，一次计算最多缓存三个结果。从这个方面考虑，运算速度理论上是会比前面的方案快的。

动态规划解决方案

斐波那契数列求和除了可以用递归的方法解决，还可以用动态规划的方法解决。由于我是算法渣，对动态规划了解不多，只懂一点点皮毛，所以这里就不解释动态规划的概念了。（一不小心又挖了一个坑，逃）

直接贴代码好了：

function fibonacci(n) {
    let n1 = 1,
        n2 = 1,
        sum = 1
    for(let i = 3; i <= n; i += 1) {
        sum = n1 + n2
        n1 = n2
        n2 = sum
    }
    return sum
}

尾递归方案

在ES6规范中，有一个尾调用优化，可以实现高效的尾递归方案。（感谢李引证的提醒）

"use strict"
function fibonacci(n, n1, n2) {
    if(n <= 1) {
        return n2
    }
    return fibonacci(n - 1, n2, n1 + n2)
}

ES6的尾调用优化只在严格模式下开启，正常模式是无效的。

通项公式方案

斐波那契数列是有通项公式的，但通项公式中有开方运算，在js中会存在误差，而fib函数中的Math.round正式解决这一问题的。（感谢公子的指导）

function fibonacci(n){
    var sum = 0
    for(let i = 1; i <= n; i += 1) {
        sum += fib(i)
    }
    return sum

    function fib(n) {
      const SQRT_FIVE = Math.sqrt(5);
      return Math.round(1/SQRT_FIVE * (Math.pow(0.5 + SQRT_FIVE/2, n) - Math.pow(0.5 - SQRT_FIVE/2, n)));
    }
}

结语

只要注意细节，我们的代码还是有很大的优化空间的。有时候，你可能会疑惑，优化前后的性能没有明显的变化。我认为，那是你的应用规模或者数据量不够大而已，当它们大到一定程度的时候，优化的效果就很明显了。优化还是要坚持的，万一哪一天我们接手大型应用呢？

云服务器 GPU云服务器波那契数列 js页面数据的求和 js数组求和 js中的6大数据类型以及应用

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

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

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实现斐波那契数列

摘要：前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结使用实现。题目介绍斐波那契数列又被称为黄金分割数列，指的是这样的一个数列，它有如下递推的方法定义是正整数，请使用实现斐波那契函数。前言前几天面试被问到了斐波那契数列的实现以及优化的问题，当时现场卡了挺久的，现在进行一下总结（使用js实现）。题目介绍斐波那契数列又被称为黄金分割数列，指...

alexnevsky 2019-08-26 13:36 评论0 收藏0
从斐波那契数列看递归和动态规划

摘要：大名鼎鼎的斐波那契数列，，，，，，，，使用数学归纳法可以看出其规律为。对于斐波那契数列的求解，有自顶向下的记忆化搜索递归和自下向上的迭代法，他们都使用了动态规划的思想。大名鼎鼎的斐波那契数列：0，1，1，2，3，5，8，13，21...使用数学归纳法可以看出其规律为：f(n) = f(n-1) + f(n-2)。递归下面首先直接使用递归（JavaScript实现）来求解第 n ...

charles_paul 2019-08-22 18:30 评论0 收藏0
递归

摘要：递归概念递归是一种针对简单循环难以编程实现的问题，通过函数调用自身，提供优雅解决方案的技术。拥有基础情况或终止条件来停止递归。这个称之为递归调用。为了避免重新创建字符串，使用递归辅助方法来进行改良。递归概念递归是一种针对简单循环难以编程实现的问题，通过函数调用自身，提供优雅解决方案的技术。递归都具有以下三个要点：使用 if-else 或 switch 语句来引导不同的情况。 ...

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

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

Galence 2019-08-26 12:01 评论0 收藏0