i******t 发帖数: 22541 | 1 f(n) = f(n-1)+f(n-2)
所以总共树的高度是 n , 每i层的节点数 2^i
所以总共节点数 2^0 + 2^1 +... +2^n >2^n
所以
错略复杂度是 THETA(2^n)
?
所以是 np-hard 问题? |
a*****u 发帖数: 1712 | 2 复杂度是O(n)
念order of,不是theta
Np-hard好像也不是你说的那样定义的
★ 发自iPhone App: ChineseWeb 7.8
【在 i******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : f(n) = f(n-1)+f(n-2) : 所以总共树的高度是 n , 每i层的节点数 2^i : 所以总共节点数 2^0 + 2^1 +... +2^n >2^n : 所以 : 错略复杂度是 THETA(2^n) : ? : 所以是 np-hard 问题?
|
i******t 发帖数: 22541 | 3 O(n) 是 big O啊 还有个 Theta啊
【在 a*****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 复杂度是O(n) : 念order of,不是theta : Np-hard好像也不是你说的那样定义的 : : ★ 发自iPhone App: ChineseWeb 7.8
|
a*****u 发帖数: 1712 | 4 theta是什么?上下限吗?一般面试big O就行了吧,不需要上下限吧
★ 发自iPhone App: ChineseWeb 7.8
【在 i******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(n) 是 big O啊 还有个 Theta啊
|
a*****u 发帖数: 1712 | 5 网上查的
Big-O is an upper bound.
Big-Theta is a tight bound, i.e. upper and lower bound.
When people only worry about what's the worst that can happen, big-O is
sufficient; i.e. it says that "it can't get much worse than this". The
tighter the bound the better, of course, but a tight bound isn't always easy
to compute.
Fibonacci 的upper bound肯定是O(n)的
★ 发自iPhone App: ChineseWeb 7.8
【在 a*****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : theta是什么?上下限吗?一般面试big O就行了吧,不需要上下限吧 : : ★ 发自iPhone App: ChineseWeb 7.8
|
i******t 发帖数: 22541 | 6 一个是 big O 还有个 sigma 还有个 theta
。。。
theta 和 O正好相反
sigma 是 加中间。。。
【在 a*****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : theta是什么?上下限吗?一般面试big O就行了吧,不需要上下限吧 : : ★ 发自iPhone App: ChineseWeb 7.8
|
e*****w 发帖数: 144 | 7 fibonacci是O(log n).
【在 i******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个是 big O 还有个 sigma 还有个 theta : 。。。 : theta 和 O正好相反 : sigma 是 加中间。。。
|
b**********5 发帖数: 7881 | 8 是O(n)吧。 怎么搞O(lgn)?
【在 e*****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : fibonacci是O(log n).
|
L********e 发帖数: 159 | 9 NP-hard不是这么定义的,Fibonacci这种有closed form solution的问题在theory里应
该算O(1) |
i******t 发帖数: 22541 | 10 我说错了
我应该说的是 这种用原始递归做的时候的复杂度 是 大约 2^n
用 DP 是可以o(n)的
还有个方法是 logn
easy
【在 a*****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 网上查的 : Big-O is an upper bound. : Big-Theta is a tight bound, i.e. upper and lower bound. : When people only worry about what's the worst that can happen, big-O is : sufficient; i.e. it says that "it can't get much worse than this". The : tighter the bound the better, of course, but a tight bound isn't always easy : to compute. : Fibonacci 的upper bound肯定是O(n)的 : : ★ 发自iPhone App: ChineseWeb 7.8
|
|
|
b**********5 发帖数: 7881 | 11 怎么搞O(lgn)
【在 i******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我说错了 : 我应该说的是 这种用原始递归做的时候的复杂度 是 大约 2^n : 用 DP 是可以o(n)的 : 还有个方法是 logn : : easy
|
L********e 发帖数: 159 | 12 [fn+1]=[1, 1][fn ]
[fn ] [1, 0][fn-1]
然后参考矩阵乘积的logn解法。
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么搞O(lgn)
|
w**s 发帖数: 339 | 13 别搞什么O(logN)了。你要是较真的话,既然写成矩阵,还可以算矩阵的特征值和特征
向量,然后可以可以写出通项公式,那就是O(1)了。有兴趣可以翻翻组合数学的书。方
法我还记得,但特征值不记得了。好像跟黄金分割有关。所以我们写程序O(N)就可以了
。 |
B******5 发帖数: 4676 | 14 那请问如何在O(1)算根号5的n次方?
【在 w**s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 别搞什么O(logN)了。你要是较真的话,既然写成矩阵,还可以算矩阵的特征值和特征 : 向量,然后可以可以写出通项公式,那就是O(1)了。有兴趣可以翻翻组合数学的书。方 : 法我还记得,但特征值不记得了。好像跟黄金分割有关。所以我们写程序O(N)就可以了 : 。
|
c********p 发帖数: 1969 | 15 我太笨了,不得不用一个数来试了一下,发现是2^n |