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。
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- ♂ (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- ♂ (0 bytes) () 06/12/2019 postreply 15:57:57
• 这个不一定, FIBONACCI很慢是因为子问题重复出现。 所以可用MEMOIZATION, 马上变得很快 -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- ♂ (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