百科问答小站 logo
百科问答小站 font logo



递归和循环相比耗费更多的空间,对于循环来说除了可以简化逻辑外还有什么优点吗? 第1页

  

user avatar   zhai-sen-8 网友的相关建议: 
      

比如说dp,一种实现方式就是自底向上的循环,另一种实现方式是自顶向下的memoization(用递归)。关键就在于,如果使用循环来实现,就要自己确定遍历次序,但memoization是自动遍历的,不需要你亲自确定次序。很多时候,要想自己确定遍历次序是很困难的,甚至是几乎做不到的;即使可以做到,遍历的顺序也未必和memoization一样。如果循环的遍历顺序更差(意思是重复遍历的很多),那么时间上就不如递归。(我听人说过在一种背包问题中循环的时间大概长了30%)

举个例子,我之前看过的回答,计算斐波那契数列的一种比较快速的算法是利用如下的递推式:

写个memoization的递归是容易的。但想想如何自底向上循环?直接从小到大往上循环可是 的。




  

相关话题

  有什么你相见恨晚的轮子? 
  是不是机器学习的框架都偏向 Python ?如果是,为什么? 
  开始慢慢抄代码敲对自己编程提高有用吗? 
  孩子一年级成绩不理想,朋友建议可以学学少儿编程,学习少儿编程对提高孩子的逻辑思维能力真的有帮助吗? 
  python是用C实现的,Java是用C++实现的,那为什么不直接用C或C++呢? 
  从1分钟图上起笔递归至月线级别走势,这个工作量有多大吗? 
  在这种不同操作下,对于计算机体系的不同是否会造成时间差异? 
  为什么迷宫从终点向起点走更容易? 
  你遇见过什么当时很有潜力但是最终没有流行的深度学习算法? 
  为什么美国程序员工作比中国程序员工作轻松、加班少? 

前一个讨论
如何评价在 LG 杯 16 强赛上,柯洁战胜申真谞,在世界第一人之争中再下一城?
下一个讨论
作曲技术理论发展到极致,将会变成一种怎样的形态?





© 2025-04-03 - tinynew.org. All Rights Reserved.
© 2025-04-03 - tinynew.org. 保留所有权利