Re: [理工] [資結]-時間複雜度

[linesx3 (小李)]

※ 引述《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
推 FRAXIS:如果f(n)比g(n)大 為甚麼答案是FALSE?
→ opcan:g(n)比較大吧 階層>次方
→ linesx3:真的，剛才看太快我錯了不好意思
推 converse2006:如果你有背費氏數列的推導應該就知道約為2^n 兩個取
→ converse2006:log 會得f(n)=nlog2 g(n)=nlogn則f(n)=O(g(n))
推 yesa315:了解 謝謝