空间换时间,把递归的时间复杂度降低到O(2n)

  递归算法的时间复杂度除非只有前两项,否则都不是线性的,并且相当耗费内存。我们用最常见的的fibonacci数列来说明:

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

   这是一种最常见的写法,这种写法极其耗费内存,当参数n大于30时,就会明显感觉到花的时间比较长,如果n等于100,浏览器极有可能会崩溃掉。

  我们来分析一下耗费内存和时间原因:先将要计算的变量值存到堆栈中,不停地使用栈,保存现场,直到递归结束条件满足时,才从堆栈中取出要计算的变量值,再一一恢复现场,计算得到最终结果。

  我们通过一张图来看一下这个递归的调用过程:

  我们可以看到,当n为4时,一共进行了12步运算,其中第6、8、9、10、11步是重复的。正是这些重复的地方造成了这个递归的低效。

  既然找到了原因所在,那么我们怎么来改进呢?

  从原因下手,原因是之前的计算结果没有保存,造成了重复计算,那么我们就把之前的计算结果用一个变量保存起来,修改后的代码如下:

var fibonacci=(function(){
    var temp={},
        value;
    function f(n){
        if(n in temp){
            value=temp[n];
        } else {
            if( n === 0 || n === 1){
                value = n;
            } else {
                value = f(n - 1) + f(n - 2);
            }
            temp[n] = value;
        }
        return value;
    }
    return f;
})();

  这里我们引入了一个变量temp来存储前面的计算结果,这种做法就是以空间换时间的做法。由于递归总是要到达最底层,然后再回到最顶层,所以时间复杂度最小为O(2n),我们修改后的递归算法时间复杂度即为O(2n)。

  最后,我们来测试一下计算n为100的情况时间和计算次数:

  我们可以看到,时间很短,计算次数只有199次。如果用没有优化的代码,我的浏览器会崩溃掉。

  希望本文对大家有所帮助,欢迎留言讨论。

  本文首发博客园:http://jscode.cnblogs.com,转载请注明出处。


AD:【腾讯云服务器大降价】2核4G 222元/3年 1核2G 38元/年

AD:【腾讯云服务器大降价】2核4G 222元/3年 1核2G 38元/年

本文来自一日成建站教程网https://www.yiricheng.cn/),为广大编程爱好者提供零基础快速搭建博客网站的方法,分享计算机网络、HTML、CSS、JavaScript、PHP、响应式设计以及Python自动化办公的博客文章,另有各类小工具、电子书、免费教程。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

相关阅读  前端攻城狮学习笔记四:点击ul下的li时alert其index值(闭包的应用)