有些问题直接用recursion来implement会产生exponential time

来源: 2019-06-12 15:50:50 [] [博客] [旧帖] [给我悄悄话] 本文已被阅读: 次 (366 bytes)

complexity。一个很好的例子就是 Fibonacci sequence 的计算。

f(n) = f(n-1) + f(n-2)

f(0) = 0

f(1) = 1

直接 top-down 用 recursion 计算会产生 exponential time complexity。得要 bottom-up 往上堆积才会产生 linear time complexity。

 

 



斯坦福工作10年后,她告诉家长养育孩子这3条红线不能碰

美国孩子要看的8000本学科阅读书单里藏着什么秘密?

The Land of Stories紅透全球 90后天才作家代表作

好书推荐:I Survived 系列- 理解灾难,理解历史,还是逃生指南!

《推介》给全职推爸推妈推荐两本爬藤指南书

让孩子爱上阅读,那些必须收藏的儿童经典读物

美国当下最流行的STEM玩具(4-15岁)

350万美国读者票选出:20本今年最受欢迎的书(组图)

推荐适合小朋友看的英文绘本

好书推荐:“All the Light We Cannot See” by Anthony Doerr

推荐一本历史小书,主要是欧洲史

2015年看的几本书

我在北京雾霾时用这个面具!

强力推荐的一本好书,家长不妨买一本来读读(图)

家有5年级的男娃全家必看的一本书


减少疲劳:给网虫们推荐一样非常适用的东西

一个小小的的detector或许会挽救很多人的生命

正在看一本帮助男孩成长的书,一点笔记

推荐两本新书,应该对孩子的思维很有帮助

给大家推荐一本书 希望培养孩子研究科学的家长看

推荐Wordly Wise 3000的书

犹太推儿经:看到B-,犹爸会不会怒发冲kipa?

强烈推荐给大人孩子都要读:高效能孩子的七个习惯

推荐一本家有 Teenager 的好书

想知道如何进理想大学?推荐二本书,很有帮助

有关孩子阅读,介绍一套相当不错的书

推荐一本书 Gifted Lives by Joan Freeman

所有跟帖: 

可以用MEMOIZATION提高RECURSSION的效率, 还DYNAMIC PROGRAMMING相似 -deepsigh- 给 deepsigh 发送悄悄话 deepsigh 的博客首页 deepsigh 的个人群组 (0 bytes) () 06/12/2019 postreply 15:54:54

就用dp 就行了,不一定到线性但可以转成polynomial complexity -阿拉拉- 给 阿拉拉 发送悄悄话 阿拉拉 的个人群组 (0 bytes) () 06/12/2019 postreply 15:56:11

讲讲 -柳伊伊- 给 柳伊伊 发送悄悄话 柳伊伊 的个人群组 (49 bytes) () 06/12/2019 postreply 15:58:49

泛泛的说吧,如果你是卖东西的,帮你预测你需要进多少货,货物在仓库怎么放最优化,你怎么跟客户推荐要买啥 -阿拉拉- 给 阿拉拉 发送悄悄话 阿拉拉 的个人群组 (333 bytes) () 06/12/2019 postreply 16:14:12

新款 -柳伊伊- 给 柳伊伊 发送悄悄话 柳伊伊 的个人群组 (209 bytes) () 06/12/2019 postreply 16:37:16

是啊,生活中其实有很多呢,只是大家不觉得而已 -阿拉拉- 给 阿拉拉 发送悄悄话 阿拉拉 的个人群组 (368 bytes) () 06/12/2019 postreply 16:45:34

哈哈 -柳伊伊- 给 柳伊伊 发送悄悄话 柳伊伊 的个人群组 (35 bytes) () 06/12/2019 postreply 16:47:31

干嘛有些啊。所有傻递归都是Exponential的,复杂性是O(n!) -skyport- 给 skyport 发送悄悄话 skyport 的博客首页 skyport 的个人群组 (0 bytes) () 06/12/2019 postreply 15:57:57

这个不一定, FIBONACCI很慢是因为子问题重复出现。 所以可用MEMOIZATION, 马上变得很快 -deepsigh- 给 deepsigh 发送悄悄话 deepsigh 的博客首页 deepsigh 的个人群组 (0 bytes) () 06/12/2019 postreply 16:00:15

不是啊,recursive Fibonacci roughly是2^n 吧,divide & conquer类的好多nlogn -阿拉拉- 给 阿拉拉 发送悄悄话 阿拉拉 的个人群组 (0 bytes) () 06/12/2019 postreply 16:25:53

关键词“傻递归”LOL。好吧修改下,每一步非常数的递归的复杂性是指数级的 -skyport- 给 skyport 发送悄悄话 skyport 的博客首页 skyport 的个人群组 (0 bytes) () 06/12/2019 postreply 16:49:03

啊,太不精确了。 -古代的事物- 给 古代的事物 发送悄悄话 古代的事物 的个人群组 (58 bytes) () 06/12/2019 postreply 16:58:16

有算法,有分析在后,升改进版,Premium 用户要付费的哦:) -网恋无罪- 给 网恋无罪 发送悄悄话 网恋无罪 的博客首页 网恋无罪 的个人群组 (2452 bytes) () 06/12/2019 postreply 17:05:56

加跟帖:

  • 笔名:      密码: 保持登录状态一个月,直到我退出登录。
  • 标题:
  • 内容(可选项): [所见即所得|预览模式] [HTML源代码] [如何上传图片] [怎样发视频] [如何贴音乐]
回到顶部