JavaScript程序设计高级算法之动态规划实例分析

本文实例讲述了JavaScript程序设计高级算法之动态规划。分享给大家供大家参考，具体如下：

主要是看了《数据结构与算法》有所感悟，虽然这本书被挺多人诟病的，说这有漏洞那有漏洞，但并不妨碍我们从中学习知识。

其实像在我们前端的开发中，用到的高级算法并不多，大部分情况if语句，for语句，swith语句等等，就可以解决了。稍微复杂的，可能会想到用递归去的解决。

但要注意的是递归写起来简洁，但实际上执行的效率并不高。

我们再看看动态规划的算法：

动态规划解决方案从底部开始解决问题， 将所有小问题解决掉， 然后合并成一个整体解决方案， 从而解决掉整个大问题 。

实例举例  （计算斐波那契数列）

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........

这个数列从第3项开始，每一项都等于前两项之和。

针对这个数列，可以用一个递归的函数去计算第n项 数值

// 斐波那契数列
function recurFib(n) {
    if(n < 2){
      return n ;
    }else {
//          document.write("第"+(n-1)+"次计算 n-1="+(n-1)+recurFib(n-1)+'   ');
//          document.write("n-2="+(n-2)+recurFib(n-2)+"<br>");
      return recurFib(n-1)+recurFib(n-2)
    }
}

确实是个非常简洁的代码，上面有被注释的代码 ，是用来打印出当n=多少，要执行多少次函数，不过明眼人一眼就能看出来执行的次数随着n的变大，次数也会非常恐怖增长。

当n=5的时候，递归树已经长的很大了……可以预见当n=10，甚至n=100的时候……

明白了递归函数执行效率之差，我们再来看的动态规划是如何做的

function dynFib(n) {
  let val = [];
  for(let i = 0; i <= n; ++i){
    val[i]=0;
  }
  if(n ===1 || n === 2){
    return 1;
  }
  else {
    val[1] =1;
    val[2] = 2;
    for(let i = 3; i <= n; ++i){
      val[i] = val [i-1] +val[i-2] ;
    }
  }
  return val[n-1]
}

通过数组 val 中保存了中间结果， 如果要计算的斐波那契数是 1 或者 2， 那么 if 语句会返回 1。 否则，数值 1 和 2 将被保存在 val 数组中 1 和 2 的位置。

循环将会从 3 到输入的参数之间进行遍历， 将数组的每个元素赋值为前两个元素之和， 循环结束， 数组的最后一个元素值即为最终计算得到的斐波那契数值， 这个数值也将作为函数的返回值。

接下来可以写个简单的测试函数，来对比两者的运行时间。

// 定义一个测试函数，将待测函数作为参数传入
function test(func,n){
  let start = new Date().getTime();//起始时间
  let res = func(n);//执行待测函数
  document.write('<br>'+'当n='+n+'的时候 '+res+'<br>');
  let end = new Date().getTime();//结束时间
  return (end - start)+"ms";//返回函数执行需要时间
}

打印函数执行

let time = test(recurFib,40);
document.write(time);
let time2 = test(dynFib,40);
document.write(time2);

结果如下：

最后， 你或许已经意识到在使用迭代的方案计算斐波那契数列时， 是可以不使用数组的。

需要用到数组的原因是因为动态规划算法通常需要将中间结果保存起来。

以下是迭代版本的斐波那契函数义

function iterFib(n) {
  let last = 1;
  let nextLast = 1;
  let result = 1;
  for (let i = 2; i < n; ++i) {
    result = last + nextLast;
    nextLast = last;
    last = result;
  }
  return result;
}

当然这个迭代版本的与数组的版本的效率也是相同的。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

赞 (0)

相关推荐

  • JavaScript实现树的遍历算法示例【广度优先与深度优先】

    JavaScript实现树的遍历算法示例【广度优先与深度优先】

    本文实例讲述了JavaScript实现树的遍历算法.分享给大家供大家参考,具体如下: <script type="text/javascript"> var t = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]; //下面这段深度优先搜索方法出自Aimingoo的[JavaScript语言精髓与编程实践] var deepView = function(aTree,iNode) { (iNode in aTree)

  • JS笛卡尔积算法与多重数组笛卡尔积实现方法示例

    本文实例讲述了JS笛卡尔积算法与多重数组笛卡尔积实现方法.分享给大家供大家参考,具体如下: js 笛卡尔积算法的实现代码,据对象或者数组生成笛卡尔积,并介绍了一个javascript多重数组笛卡尔积的例子,以及java实现笛卡尔积的算法与实例代码. 一.javascript笛卡尔积算法代码 例子,根据对象或者数组生成笛卡尔积. //笛卡儿积组合 function descartes(list) { //parent上一级索引;count指针计数 var point = {}; var resul

  • 几种经典排序算法的JS实现方法

    一.冒泡排序 function BubbleSort(array) { var length = array.length; for (var i = length - 1; i > 0; i--) { //用于缩小范围 for (var j = 0; j < i; j++) { //在范围内进行冒泡,在此范围内最大的一个将冒到最后面 if (array[j] > array[j+1]) { var temp = array[j]; array[j] = array[j+1]; arra

  • 原生js的RSA和AES加密解密算法

    本文实例为大家分享了js中RSA和AES加密解密详细代码,供大家参考,具体内容如下 <!doctype html> <html> <head> <meta charset='UTF-8'> </head> <body> <div class='test'></div> <script type="text/javascript"> function encrypt(data, k

  • JavaScript数据结构与算法之队列原理与用法实例详解

    JavaScript数据结构与算法之队列原理与用法实例详解

    本文实例讲述了JavaScript数据结构与算法之队列原理与用法.分享给大家供大家参考,具体如下: 队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素.队列用于存储按顺序排列的数据,先进先出,这点和栈不一样(后入先出).在栈中,最后入栈的元素反而被优先处理.我们现在可以把队列想象对我们去餐馆吃饭的情景,很多人排队吃饭,排在最前面的人先打饭.新来的人只能在后面排队.直到轮到他们为止. 一:对队列的操作 队列有2种主要的操作,向队尾中插入新元素enqueue()方法和删除队列中的队首的元

  • js版本A*寻路算法

    说到做游戏,必不可少的需要用到寻路算法,一般游戏里的寻路算法大多数都以A*算法为主,这里也就实现了js里采用a*寻路的程序,在51js和蓝色都开了帖. 程序是以前写的,后来也没有修正或者精简,有冗余之处大家还见谅一下. 当然,这个寻路算法也不是最优化的,像幻宇开发的"交点寻径法"也是个中精品,两者可谓各有千秋,只是如果地图很大的情况下,我们会惊讶于"交点寻径法"的迅速. use A* to find path... /* written by 百晓生 email:j

  • javascript算法之二叉搜索树的示例代码

    什么是二叉树 二叉树就是树的每个节点最多只能有两个子节点 什么是二叉搜索树 二叉搜索树在二叉树的基础上,多了一个条件,就是二叉树在插入值时,若插入值比当前节点小,就插入到左节点,否则插入到右节点:若插入过程中,左节点或右节点已经存在,那么继续按如上规则比较,直到遇到一个新的节点. 二叉搜索树的特性 二叉搜索树由于其独特的数据结构,使得其无论在增删,还是查找,时间复杂度都是O(h),h为二叉树的高度.因此二叉树应该尽量的矮,即左右节点尽量平衡. 二叉搜索树的构造 要构造二叉搜索树,首先要构造二叉树

  • JavaScript实现的贝塞尔曲线算法简单示例

    本文实例讲述了JavaScript实现的贝塞尔曲线算法.分享给大家供大家参考,具体如下: 如果在HTML5支持好的浏览器中,可以看到用svg绘制的路径线. 在所有浏览器中,均可以看到一个小方块沿着贝塞尔曲线路径来回运动. 效果图: 主要代码: <div style="position:absolute;left:0;top:0;width:500px;height:300px;overflow:hidden;"> <svg id="root" wi

  • javascript常用经典算法实例详解

    javascript常用经典算法实例详解

    本文实例讲述了javascript常用算法.分享给大家供大家参考,具体如下: 入门级算法-线性查找-时间复杂度O(n)--相当于算法界中的HelloWorld //线性搜索(入门HelloWorld) //A为数组,x为要搜索的值 function linearSearch(A, x) { for (var i = 0; i < A.length; i++) { if (A[i] == x) { return i; } } return -1; } 二分查找(又称折半查找) - 适用于已排好序的

  • JavaScript程序设计高级算法之动态规划实例分析

    本文实例讲述了JavaScript程序设计高级算法之动态规划.分享给大家供大家参考,具体如下: 主要是看了<数据结构与算法>有所感悟,虽然这本书被挺多人诟病的,说这有漏洞那有漏洞,但并不妨碍我们从中学习知识. 其实像在我们前端的开发中,用到的高级算法并不多,大部分情况if语句,for语句,swith语句等等,就可以解决了.稍微复杂的,可能会想到用递归去的解决. 但要注意的是递归写起来简洁,但实际上执行的效率并不高. 我们再看看动态规划的算法: 动态规划解决方案从底部开始解决问题, 将所有小问题

  • JavaScript股票的动态买卖规划实例分析下篇

    目录 1. 最佳买卖股票时机含冷冻期 题目描述 题解 2. 买卖股票的最佳时机 III 题目描述 题解 1. 最佳买卖股票时机含冷冻期 题目描述 给定一个整数数组prices,其中第prices[i]表示第i天的股票价格 . 设计一个算法计算出最大利润.在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天). 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票). 示例 1: 输入: prices = [

  • JavaScript多种滤镜算法实现代码实例

    这篇文章主要介绍了JavaScript多种滤镜算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.灰色滤镜 设定R,G,B值相等 function makeGray(img){ for(var pixel of img.values()){ var avg = (pixel.getRed()+pixel.getGreen()+pixel.getBlue())/3; pixel.setRed(avg); pixel.setGree

  • javascript常见数字进制转换实例分析

    本文实例讲述了javascript常见数字进制转换的方法.分享给大家供大家参考,具体如下: 基本思路是先把其他进制的转化成 十进制,然后再转化.这个过程是利用parseInt函数,例如把一个16进制的数字(num)转化成10进制,num = parseInt(num,16). 如果再想把它转化成二进制的,就是如下:num.toString(2) . 这其中关于16进制的一个函数也很特别,escape函数可以将一个字符串转化成16进制的数字. 下面是一个综合的例子: var a = escape(

  • JavaScript事件委托原理与用法实例分析

    本文实例分析了JavaScript事件委托原理与用法.分享给大家供大家参考,具体如下: 在日常中,我们可能会听到事件委托这样的概念,有些同学可能对事件委托已经很了解了,也有些同学可能只是听过事件委托,只是会简单的使用,但是对于事件委托的原理不怎么知道.所以该博文会解释一下原生js的事件委托的原理,为什么会有事件委托,为什么可以这样用事件委托等等问题. 1. js中的事件流 在解析事件委托之前,我们先回顾一下js中的事件流,即冒泡和捕获. ① .冒泡:当下级节点触发某个事件的时候,该事件会逐级向上

  • JavaScript设计模式之责任链模式实例分析

    JavaScript设计模式之责任链模式实例分析

    本文实例讲述了JavaScript设计模式之责任链模式.分享给大家供大家参考,具体如下: 介绍 责任链模式(Chain of responsibility)是使多个对象都有机会处理请求,从而避免请求的发送者和接受者之间的耦合关系.将对象连成一条链,并沿着这条链传递该请求,直到有一个对象处理他为止. 请求以后,从第一个对象开始,链中收到请求的对象要么亲自处理它,要么转发给链中的下一个候选者.提交请求的对象并不知道哪一个对象将会处理它--也就是该请求有一个隐式的接受者(implicit receiv

  • JavaScript编程设计模式之构造器模式实例分析

    本文实例讲述了JavaScript编程设计模式之构造器模式.分享给大家供大家参考,具体如下: 经典的OOP语言中,构造器(也叫构造函数)是一个用于初始化对象的特殊方法.在JS中,因为一切皆对象,对象构造器经常被提起. 对象构造器用于建立制定类型(Class)的对象,可以接受参数用于初始化对象的属性和方法. 对象建立 在JS中,有三个常用的方法用于建立对象: //1, 推荐使用 var newObject = {}; //2, var newObject = Object.create( null

  • JavaScript中localStorage对象存储方式实例分析

    本文实例讲述了JavaScript中localStorage对象存储方式.分享给大家供大家参考,具体如下: [Local storage limitations]文章中提及JavaScript里的local storge的限制,例子中在localStorage里存储了一个bool型的数据,但是却没有像我们期待的一样进行存储. 当我们存储布尔型,数值型,字符串型时,localStorage对象会将我们存储的数据默认转为字符串字面量. localStorage[0] = false;// "fals

  • JavaScript面向对象之私有静态变量实例分析

    本文实例分析了JavaScript面向对象之私有静态变量.分享给大家供大家参考,具体如下: 大家知道,私有实例变量的原理是根据作用域. 私有实例变量是在Javascript的function内部用var关键字实现,只在function内部有效. 仿照这个,提出私有静态变量的解决方案: <script language="javascript" type="text/javascript"> var JSClass = (function() { var

  • Javascript控制div属性动态变化实例分析

    Javascript控制div属性动态变化实例分析

    本文实例分析了Javascript控制div属性动态变化的方法.分享给大家供大家参考.具体如下: 这里使用JS控制div属性变化,另Div的几何尺寸发生变化,例如变宽.变高.改变颜色.隐藏Div.重置所有属性为默认值等.虽然在本例中,这些属性值的改变很简单就可实现,但在JavaScript网页前端设计中,这种属性或方法经常会被用到,因此还是值得大家关注的. 运行效果截图如下: 在线演示地址如下: http://demo.jb51.net/js/2015/js-cha-div-opt-demo/

随机推荐