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

来源: Porcelana 于 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。

 

 

所有跟帖： 

• 可以用MEMOIZATION提高RECURSSION的效率， 还DYNAMIC PROGRAMMING相似 -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 的博客首页 (0 bytes) () 06/12/2019 postreply 15:57:57

• 这个不一定， FIBONACCI很慢是因为子问题重复出现。 所以可用MEMOIZATION， 马上变得很快 -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 的博客首页 (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

请您先登陆，再发跟帖！