作者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