查看: 1504|回复: 2
收起左侧

对动态规划的引入的问题:Stanford Algorithms: Design and Analysis, Part 2 (week3)

|只看干货 |入门|算法|数据结构, 公开课

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (102)
 
 
2% (3)    👎
公开课
学校名称: Standford
Unit号: 3
开课时间: 2016-08-08
课程全名: Stanford Algorithms: Design and Analysis, Part 2
平台: Coursera

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
I am very lost in this introduction, and ask for help to get the logic.
Here, the professor introduces four ways:1.greedy 2. divide & conquer 3.linear time 4.reconstruction.
For 1.greedy, it may produce a not maxium result. So it's out.
For 2.divide & conquer, it takes exponential time, too slow. So it's out.
Here, it comes my confusion.
I can't figure out the difference between linear time and reconstruction. Why it costs O(n) and What's the fill-in array used for?
Are both of 3.linear time and 4.reconstruction Dynamical Programming?

感谢大家的帮助!


上一篇:Git公开课推荐
下一篇:召集学习Programming Languages Part A的小伙伴
sprayfly 2016-8-17 01:16:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   84% (629)
 
 
15% (118)    👎
本帖最后由 sprayfly 于 2016-8-17 01:23 编辑

I can't figure out the difference between linear time and reconstruction. Why it costs O(n)
不知道你上过part I没有,里面讲了时间复杂度的分析吧。dynamic programming和recursion最重要的区别之一就是它复用了以前计算过的subproblem的optimal solution,而不是重复的计算,这就大大节约的时间。这里的cost O(n)只是针对你说的例子,不同情况还得你自己分析。比如到了knapsack problem你会发现其实是pseudo-polynomial。

and What's the fill-in array used for?s
这个table用来reconstruct optimal solution,因为dynamic programming通常得到的是你求的最优的value,而不是解决方法。比如你用dynamic programming 实现Bellman-Ford,得到的只是最短路径的值,但你想知道的是该走哪些edge? 这就需要这个fill-in table来重构了(当然,有时候可以optimal space,不用整个table,这就需要在dynamic programming循环里面做一些标记,记录一些重要信息了)
回复

使用道具 举报

 楼主| 吉他的小晴天 2016-8-17 09:54:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (102)
 
 
2% (3)    👎
sprayfly 发表于 2016-8-17 01:16
I can't figure out the difference between linear time and reconstruction. Why it costs O(n)
不知道 ...

非常感谢你!!!
讲的很清晰!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表