[理工] [資結] 一題遞迴式

[boy5548 (小YO)]

請問一下，T(n)=3T(n/5)+nlgn，這個遞迴式該怎麼解? 謝謝!

還有2^n=o(2^n) 為什麼是false?

不是可以找到兩正常數c=2,n0=1 使得 2^n < c˙2^n  for all n>=n0嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.171.45.198
→ boy5548:希望版大們可以順便附上過程
※ 編輯: boy5548         來自: 118.171.45.198       (01/29 23:20)
→ dy957:第二題如果當n夠大等號會成立吧 用極限來看要讓它趨近0才行
推 QoiiwWe:第一題是Master Theorem吧 O(nlgn)嗎?
→ dy957:第一題好像不能用@@??
→ boy5548:對阿 第一題好像不能用...
→ boy5548:所以說如果等號可以成立 他就不能寫成o? <不是包含在<=嗎
→ dy957:對,因為包含在裡面所以更嚴苛..我記得證小o跟用極限趨進0
→ dy957:是等價的 大O的極限就可以是常數或0
→ cksh3300110:@_@ 第一題可以用MASTER THEOREM
→ qqoil:n^log(5)3 < n < nlogn 所以用master定理解就好
→ dy957:但是ε取的到嗎?
→ qqoil:ε取 -log(5)3+1 > 0成立
→ dy957:喔喔,謝謝
→ sneak: 第一題是Master  https://daxiv.com