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 的大作中提到】
: 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 的大作中提到】
: 复杂度是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 的大作中提到】
: 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 的大作中提到】
: theta是什么？上下限吗？一般面试big O就行了吧，不需要上下限吧
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
i******t
发帖数: 22541 | 6 一个是 big O 还有个 sigma 还有个 theta
。。。
theta 和 O正好相反
sigma 是 加中间。。。
【在 a*****u 的大作中提到】
: theta是什么？上下限吗？一般面试big O就行了吧，不需要上下限吧
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
e*****w
发帖数: 144 | 7 fibonacci是O(log n).
【在 i******t 的大作中提到】
: 一个是 big O 还有个 sigma 还有个 theta
: 。。。
: theta 和 O正好相反
: sigma 是 加中间。。。
|
b**********5
发帖数: 7881 | 8 是O(n)吧。 怎么搞O(lgn)?
【在 e*****w 的大作中提到】
: 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 的大作中提到】
: 网上查的
: 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 的大作中提到】
: 我说错了
: 我应该说的是 这种用原始递归做的时候的复杂度 是 大约 2^n
: 用 DP 是可以o(n)的
: 还有个方法是 logn
:
: easy
|
L********e
发帖数: 159 | 12 [fn+1]=[1, 1][fn ]
[fn ] [1, 0][fn-1]
然后参考矩阵乘积的logn解法。
【在 b**********5 的大作中提到】
: 怎么搞O(lgn)
|
w**s
发帖数: 339 | 13 别搞什么O(logN)了。你要是较真的话，既然写成矩阵，还可以算矩阵的特征值和特征
向量，然后可以可以写出通项公式，那就是O(1)了。有兴趣可以翻翻组合数学的书。方
法我还记得，但特征值不记得了。好像跟黄金分割有关。所以我们写程序O(N)就可以了
。 |
B******5
发帖数: 4676 | 14 那请问如何在O（1）算根号5的n次方？
【在 w**s 的大作中提到】
: 别搞什么O(logN)了。你要是较真的话，既然写成矩阵，还可以算矩阵的特征值和特征
: 向量，然后可以可以写出通项公式，那就是O(1)了。有兴趣可以翻翻组合数学的书。方
: 法我还记得，但特征值不记得了。好像跟黄金分割有关。所以我们写程序O(N)就可以了
: 。
|
c********p
发帖数: 1969 | 15 我太笨了，不得不用一个数来试了一下，发现是2^n |
