作者linesx3 (小李)
看板Grad-ProbAsk
标题Re: [理工] [资结]-时间复杂度
时间Tue Dec 15 22:45:27 2009
※ 引述《yesa315 (XD)》之铭言：
: f(n)=f(n-1)+f(n-2) , g(n)=n! ,f(n)=Ω(g(n))
: 为FALSE
: 有高手可以解释一下 f(n)的复杂度吗?
: 谢谢
他是费氏数列，他可以写成一个数的次方，所以才会比g(n)还要大
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.200.65
1F：推 FRAXIS:如果f(n)比g(n)大 为甚麽答案是FALSE? 12/15 23:09
2F：→ opcan:g(n)比较大吧 阶层>次方 12/15 23:16
3F：→ linesx3:真的，刚才看太快我错了不好意思 12/15 23:44
4F：推 converse2006:如果你有背费氏数列的推导应该就知道约为2^n 两个取 12/16 01:04
5F：→ converse2006:log 会得f(n)=nlog2 g(n)=nlogn则f(n)=O(g(n)) 12/16 01:06
6F：推 yesa315:了解 谢谢 12/16 13:36