我们学校CS本科只有我一个正宗F1

一木菩提UID: 2390164

恩 有一次面试被问过怎么算f(n)
第一反应就是通项公式 2分之根号5+—1的n次方
他让我再想一个 于是递归
还要我再想，就for循环了.
最后再问了下递归和循环的优劣

一木菩提UID: 2390164

算法的基础章节
nynyaaa 发表于 2012-3-30 12:50

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

AmerigoUID: 2140122

围观LS扭腰金融男们的天书谈话。。。

nynyaaaUID: 204913

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

你觉得通项公式的时间复杂度大还是dp大

nynyaaaUID: 204913

围观LS扭腰金融男们的天书谈话。。。
Amerigo 发表于 2012-3-30 13:17

学术大拿不要调戏我了

AmerigoUID: 2140122

学术大拿不要调戏我了
nynyaaa 发表于 2012-3-30 13:22

问学术为何物，文盲我表示不知道。。。

VettelUID: 2684452

递归算f(n)是exponential time，重复了太多的相同计算，电脑吃不消。

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

VettelUID: 2684452

斐波那契数列这个问题好理解，不管是递归还是bottom-up我都写过真代码。

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

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

VettelUID: 2684452

Operation Research也讲这个的
诸如 贪婪算法啊 MST也讲的..
一木菩提 发表于 2012-3-30 13:15

嗯，我们也讲贪婪算法。MST还没学 orz

nynyaaaUID: 204913

斐波那契数列这个问题好理解，不管是递归还是bottom-up我都写过真代码。

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

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

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

nynyaaaUID: 204913

递归算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))

乖乖hylUID: 3162682

天书。。

VettelUID: 2684452

这正是证明了你并不理解dp。f被提起是因为它的重叠子问题是已知的，下面爱循环/递归反正按照套路来就是。其他问题你要理解问题本身，给出重叠子问题的式子，也就是 Pn = F(Pn-1,)，然后按照套路做。dp的精髓在于 ...
nynyaaa 发表于 2012-3-30 23:10

中

nynyaaaUID: 204913

出

VettelUID: 2684452

这里你完全错误了。递归只是形式，是否dp都可以用递归来表示。dp由于存储了重叠子问题的解，所以这里复杂度是O(n)，不同的dp问题，如果维度不同，可能是O(nm)。做f(n)最快的应该是通项公式，O(logn M(n))
nynyaaa 发表于 2012-3-30 23:27

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

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

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