寄托天下
楼主: Vettel
打印 上一主题 下一主题

我们学校CS本科只有我一个正宗F1 [复制链接]

Rank: 9Rank: 9Rank: 9

声望
2366
寄托币
19361
注册时间
2007-8-27
精华
8
帖子
492

荣誉版主 Aquarius水瓶座 US Applicant 港澳资深筒子 Golden Apple VISA版特殊贡献 Economist

31
发表于 2012-3-30 13:14:16 |只看该作者
恩 有一次面试被问过怎么算f(n)
第一反应就是通项公式 2分之根号5+—1的n次方
他让我再想一个 于是递归
还要我再想,就for循环了.
最后再问了下递归和循环的优劣

使用道具 举报

Rank: 9Rank: 9Rank: 9

声望
2366
寄托币
19361
注册时间
2007-8-27
精华
8
帖子
492

荣誉版主 Aquarius水瓶座 US Applicant 港澳资深筒子 Golden Apple VISA版特殊贡献 Economist

32
发表于 2012-3-30 13:15:58 |只看该作者
算法的基础章节
nynyaaa 发表于 2012-3-30 12:50

Operation Research也讲这个的
诸如 贪婪算法啊 MST也讲的..

使用道具 举报

Rank: 10Rank: 10Rank: 10

声望
1185
寄托币
42086
注册时间
2005-9-20
精华
1
帖子
1041

Capricorn摩羯座 Golden Apple

33
发表于 2012-3-30 13:17:15 |只看该作者
围观LS扭腰金融男们的天书谈话。。。
Natural Redneck

使用道具 举报

Rank: 9Rank: 9Rank: 9

声望
477
寄托币
58896
注册时间
2005-4-8
精华
4
帖子
880

Aries白羊座 荣誉版主 QQ联合登录 Golden Apple

34
发表于 2012-3-30 13:21:16 |只看该作者
恩 有一次面试被问过怎么算f(n)
第一反应就是通项公式 2分之根号5+—1的n次方
他让我再想一个 于是递归
还要我再想,就for循环了.
最后再问了下递归和循环的优劣
一木菩提 发表于 2012-3-30 13:14

你觉得通项公式的时间复杂度大还是dp大
Soochow University GTER 群: 17788337 请告知所在学院,恕不接受外校


"Freedom has many difficulties and democracy is not perfect,
but we have never had to put a wall up to keep our people in,
to prevent them from leaving us." --JFK

使用道具 举报

Rank: 9Rank: 9Rank: 9

声望
477
寄托币
58896
注册时间
2005-4-8
精华
4
帖子
880

Aries白羊座 荣誉版主 QQ联合登录 Golden Apple

35
发表于 2012-3-30 13:22:53 |只看该作者
围观LS扭腰金融男们的天书谈话。。。
Amerigo 发表于 2012-3-30 13:17

学术大拿不要调戏我了
Soochow University GTER 群: 17788337 请告知所在学院,恕不接受外校


"Freedom has many difficulties and democracy is not perfect,
but we have never had to put a wall up to keep our people in,
to prevent them from leaving us." --JFK

使用道具 举报

Rank: 10Rank: 10Rank: 10

声望
1185
寄托币
42086
注册时间
2005-9-20
精华
1
帖子
1041

Capricorn摩羯座 Golden Apple

36
发表于 2012-3-30 13:24:30 |只看该作者
学术大拿不要调戏我了
nynyaaa 发表于 2012-3-30 13:22

问学术为何物,文盲我表示不知道。。。
Natural Redneck

使用道具 举报

Rank: 4

声望
9
寄托币
454
注册时间
2009-8-17
精华
0
帖子
50
37
发表于 2012-3-30 13:24:50 |只看该作者
递归算f(n)是exponential time,重复了太多的相同计算,电脑吃不消。

算斐波那契数列第n项最快的是用buttom-up,从第一项往上算,算一个记一个。

使用道具 举报

Rank: 4

声望
9
寄托币
454
注册时间
2009-8-17
精华
0
帖子
50
38
发表于 2012-3-30 13:27:46 |只看该作者
斐波那契数列这个问题好理解,不管是递归还是bottom-up我都写过真代码。

切木头,weighted interval scheduling,摆广告板,最长子数列什么的也好理解。

可是什么背包问题或者是什么没见过的问题我分析起来就无力了。

使用道具 举报

Rank: 4

声望
9
寄托币
454
注册时间
2009-8-17
精华
0
帖子
50
39
发表于 2012-3-30 13:32:14 |只看该作者
Operation Research也讲这个的
诸如 贪婪算法啊 MST也讲的..
一木菩提 发表于 2012-3-30 13:15
嗯,我们也讲贪婪算法。MST还没学 orz

使用道具 举报

Rank: 9Rank: 9Rank: 9

声望
477
寄托币
58896
注册时间
2005-4-8
精华
4
帖子
880

Aries白羊座 荣誉版主 QQ联合登录 Golden Apple

40
发表于 2012-3-30 23:10:43 |只看该作者
斐波那契数列这个问题好理解,不管是递归还是bottom-up我都写过真代码。

切木头,weighted interval scheduling,摆广告板,最长子数列什么的也好理解。

可是什么背包问题或者是什么没见过的问题我分析起来就无 ...
Vettel 发表于 2012-3-30 13:27


这正是证明了你并不理解dp。f被提起是因为它的重叠子问题是已知的,下面爱循环/递归反正按照套路来就是。其他问题你要理解问题本身,给出重叠子问题的式子,也就是 Pn = F(Pn-1,<Pn-2 ...>),然后按照套路做。dp的精髓在于找重叠子问题。
Soochow University GTER 群: 17788337 请告知所在学院,恕不接受外校


&quot;Freedom has many difficulties and democracy is not perfect,
but we have never had to put a wall up to keep our people in,
to prevent them from leaving us.&quot; --JFK

使用道具 举报

Rank: 9Rank: 9Rank: 9

声望
477
寄托币
58896
注册时间
2005-4-8
精华
4
帖子
880

Aries白羊座 荣誉版主 QQ联合登录 Golden Apple

41
发表于 2012-3-30 23:27:02 |只看该作者
递归算f(n)是exponential time,重复了太多的相同计算,电脑吃不消。

算斐波那契数列第n项最快的是用buttom-up,从第一项往上算,算一个记一个。
Vettel 发表于 2012-3-30 13:24


这里你完全错误了。递归只是形式,是否dp都可以用递归来表示。dp由于存储了重叠子问题的解,所以这里复杂度是O(n),不同的dp问题,如果维度不同,可能是O(nm)。做f(n)最快的应该是通项公式,O(logn M(n))
Soochow University GTER 群: 17788337 请告知所在学院,恕不接受外校


&quot;Freedom has many difficulties and democracy is not perfect,
but we have never had to put a wall up to keep our people in,
to prevent them from leaving us.&quot; --JFK

使用道具 举报

Rank: 9Rank: 9Rank: 9

声望
1077
寄托币
12853
注册时间
2011-8-31
精华
5
帖子
2199

枫情万种 一帆枫顺   寄托兑换店纪念章 Scorpio天蝎座 寄托优秀版主 荣誉版主

42
发表于 2012-3-31 00:01:52 |只看该作者
天书。。

使用道具 举报

Rank: 4

声望
9
寄托币
454
注册时间
2009-8-17
精华
0
帖子
50
43
发表于 2012-3-31 00:51:31 |只看该作者
这正是证明了你并不理解dp。f被提起是因为它的重叠子问题是已知的,下面爱循环/递归反正按照套路来就是。其他问题你要理解问题本身,给出重叠子问题的式子,也就是 Pn = F(Pn-1,),然后按照套路做。dp的精髓在于 ...
nynyaaa 发表于 2012-3-30 23:10

使用道具 举报

Rank: 9Rank: 9Rank: 9

声望
477
寄托币
58896
注册时间
2005-4-8
精华
4
帖子
880

Aries白羊座 荣誉版主 QQ联合登录 Golden Apple

44
发表于 2012-3-31 00:52:04 |只看该作者
Soochow University GTER 群: 17788337 请告知所在学院,恕不接受外校


&quot;Freedom has many difficulties and democracy is not perfect,
but we have never had to put a wall up to keep our people in,
to prevent them from leaving us.&quot; --JFK

使用道具 举报

Rank: 4

声望
9
寄托币
454
注册时间
2009-8-17
精华
0
帖子
50
45
发表于 2012-3-31 01:16:29 |只看该作者
这里你完全错误了。递归只是形式,是否dp都可以用递归来表示。dp由于存储了重叠子问题的解,所以这里复杂度是O(n),不同的dp问题,如果维度不同,可能是O(nm)。做f(n)最快的应该是通项公式,O(logn M(n))
nynyaaa 发表于 2012-3-30 23:27


我那个帖里说的“递归”是指不存储已知结果、每次都从第n项一直退到第一项然后再回代的递归,时间肯定是指数级的。

dp问题思考的时候是考虑最后一块和剩下的子问题,但是具体编程的时候可以从第一项开始往上算。

通项公式方法没接触过,不多说。

使用道具 举报

RE: 我们学校CS本科只有我一个正宗F1 [修改]

问答
Offer
投票
面经
最新
精华
转发
转发该帖子
我们学校CS本科只有我一个正宗F1
https://bbs.gter.net/thread-1349044-1-1.html
复制链接
发送
回顶部