专栏首页枕边书用memoization优化递归算法[JS/PHP实现]

用memoization优化递归算法[JS/PHP实现]

递归函数,通过把一个大而复杂问题简化为许多但规模较小的问题,以同一个相似模式来计算,降低了解题的难度;通过调用自身函数,极大地减少了函数代码量的优点而为开发者喜爱。但因其不断调用自身函数开辟新栈,且大量传入同样参数,得到同样的结果,重复同一行为,也会浪费大量的内存。

以经典问题,斐波那契数列为例:

斐波那契数列指的是这样一个数列: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,求其第N项的值。

对数列进行分析,我们发现,从自三项开始,第N项的值就等于其前两项之和,即第N-1和第N-2项的和。所以我们可以这样写func(n)=func(n-1)+func(n-2)

代码如下:

1 function fibonacci(n){
2     if((n==0)||(n==1)){
3         return n;
4     }else{
5       return fibonacci(n-1)+fibonacci(n-2);//调用自身函数实现递归
6     }
7 }

分析代码我们发现,计算第N项的值总要计算第0项或第1项等较小的项的值,且会进行多次运算,结果相同。在此函数内,其边界项(0、1项)简便,若是进行边界项复杂的函数,内存会大量浪费。

memoization的思想是通过定义一个数组,用来存放计算过的数据,在需要的时候直接从数组中取出,而不必再次计算,从而省去大量不必要的动作。

以下是JS实现方式:

var fibonacci=function(n){
    var cache=[];//定义一个空数组用来存放计算好的数据
  if((n==0)||(n==1)){
    return n;
  }else{
    cache[n-1]=cache[n-1]||fibonacci(n-1);//应用||或运算符“短路”的特性,若在数组中找到其值,则直接使用数组内的值,若没有,再进行计算,并将值存入数组
    cache[n-2]=cache[n-2]||fibonacci(n-2);
    return cache[n-1]+cache[n-2];//返回数组中的值
  }
}

由上可以看出,在计算过一次后,数据被存入数组,再次调用时便会优先找到数组内的值而免于大量计算,从而提升效率。

以下是PHP实现(其实差不多。。。)

function fibonacci($n){
  $cache=[];
  if(($n==0)||($n==1)){
    return $n;
  }else{
    cacehe[$n-1]=cache[$n-1]||fibonacci($n-1);
    cacehe[$n-2]=cache[$n-2]||fibonacci($n-2);
    return cache[$n-1]+cache[$n-2];
  }
}

开始总结笔记了,如有错误,请各位不吝指正,谢谢。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PHP的openssl加密扩展使用小结

    引言 互联网的发展史上,安全性一直是开发者们相当重视的一个主题,为了实现数据传输安全,我们需要保证:数据来源(非伪造请求)、数据完整性(没有被人修改过)、数据私...

    枕边书
  • Linux“体检”指标

    前言 在“求佛保佑服务器不宕机”、“杀程序员祭天”的环境下,程序员每天可谓是战战兢兢,接到电话和短信都吓得瑟瑟发抖,为了我们的安全,及时发现服务器运行问题已不仅...

    枕边书
  • 用C写一个web服务器(三) Linux下用GCC进行项目编译

    前言 离职前对做过的支付系统进行了一番#总结,继续完善我的C服务器。 本想着接下来大概实现一下 CGI 协议,但是实现过程中被一个问题卡住了: C进程与php进...

    枕边书
  • 人工智能和物联网发展推动云计算进入3.0时代

    互联网+”加速了云计算的普及,目前约有 80% 的企业用户将其IT系统运行在云中。与此同时,人工智能和物联网的发展,带动了海量终端以及海量数据交互分析的需求,进...

    哲洛不闹
  • 物联网的四种计算类型

    The-4-Computing-Types-for-the-Internet-of-Things-1068x656_副本.jpg

    用户4122690
  • “云”领生活:触手可及的云计算

    有一个楚国人出门远行.他在乘船过江的时候,一不小心,把随身带着的剑落到江中的急流里去了.船上的人都大叫:“剑掉进水里了!这个楚国人马上用一把小刀在船舷上刻了个记...

    静一
  • 云计算面临的四方面安全威胁

    这几年,云计算在IT技术领域大放异彩,成为引领技术潮流的新技术。不过云计算的发展并不是一帆风顺,也面临着不少严峻问题,尤其是安全问题,安全问题已经严重影响到了云...

    静一
  • 超级云计算:步履维艰or一帆风顺?

    当前,随着云时代的不断发展,越来越多的企业开始关注于行业当中的客户需求,不同行业客户有着不同的需求点。 对于云计算来说同样也是如此,自从云计算诞生以来,我们对于...

    静一
  • 年度最有价值AI芯片白皮书!边缘计算崛起,云+端创新架构设计

    近些年随着大数据的积聚、理论算法的革新、计算能力的提升及网络设施的发展,使得持续积累了半个多世纪的人工智能产业,又一次迎来革命性的进步,人工智能的研究和应用进入...

    刘盼
  • 清华发布《AI芯片技术白皮书》:边缘计算崛起,云+端创新架构设计

    近些年随着大数据的积聚、理论算法的革新、计算能力的提升及网络设施的发展,使得持续积累了半个多世纪的人工智能产业,又一次迎来革命性的进步,人工智能的研究和应用进入...

    新智元

扫码关注云+社区

领取腾讯云代金券