阿里云购买网站空间,中国万网,网站做任务挣钱,南海做网站公司递归算法的时间复杂度除非只有前两项#xff0c;否则都不是线性的#xff0c;并且相当耗费内存。我们用最常见的的fibonacci数列来说明#xff1a; function fibonacci(n){if( n 0 || n 1){return n;} else {return fibonacci(n - 1) fibonacci(n - 2);}
} 这是一种最常见… 递归算法的时间复杂度除非只有前两项否则都不是线性的并且相当耗费内存。我们用最常见的的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){valuetemp[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转载请注明出处。转载于:https://www.cnblogs.com/jscode/archive/2012/09/05/2671277.html
