[理工] 演算法 時間複雜度 P39 41 43

[ENGneweu (威猛先生)]

抱歉 小弟資質愚昧 又來打擾各位了

第50題

請問解答中我劃線的部分為什麼可以變成2倍的[T(1,1)+.....
https://i.imgur.com/WpkrkjQ.jpg
https://i.imgur.com/7GTDSe2.jpg

第53題

請問這題的遞迴式是怎麼出來的？
T(n)=WW(i,j)   n=j-i  但是不懂
WW(i+1,j)要怎麼變遞迴式
https://i.imgur.com/bNnbjY1.jpg


第57題

請問這題怎麼推出
T(n)>= c(n*lgn)^2 + 8c (n^2)lgn
去做substitution的？

已知此遞迴式是O(n*lgn)^2
https://i.imgur.com/juvrcAi.jpg



謝謝各位(_)

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.133.17
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1543742069.A.E77.html
※ 編輯: ENGneweu (36.231.133.17), 12/02/2018 17:16:50
※ 編輯: ENGneweu (36.231.133.17), 12/02/2018 17:17:40
※ 編輯: ENGneweu (36.231.133.17), 12/02/2018 17:33:24
推 cossetannie: 50 T(n,n)=T(1,1) T(n-1,n)=T(1,2) 後面都以此類推
→ cossetannie: 53 n=j-i 所以T(n)=T(n-1)+T(n-1)+T(n-2)
→ cossetannie: 然後T(1)=1 答案應該是O(n)嗎?
→ ENGneweu: 53懂了謝謝 答案是T(n)=O((1+√2)^n)
→ ENGneweu: 用特徵方程式解
→ ENGneweu: 50也懂了謝謝 不是很好想
推 skyHuan: 50 這是洪逸的作法
→ skyHuan: https://i.imgur.com/6FE4ZVT.jpg
推 skyHuan: 57的精神就是要假設你的猜測是對的
→ skyHuan: https://i.imgur.com/sucHoF6.jpg
→ skyHuan: 重點應該設T(k)那邊，c(klogk)^2那邊應該還可以理解因為
→ skyHuan: 要證在這個等級裡面，dk^2‧logk這項好像不能漏(我把他理
→ skyHuan: 我是覺得這個證明有點倒果為因的感覺，一直也覺得怪怪的X
→ skyHuan: D，要證P是對的先假設P再推出P正確所以得證(?)
推 skyHuan: 上面括號被切掉了...
→ skyHuan: d的那項我把他理解成要跟原函數有關係所以這項不能漏，
→ skyHuan: 詳解應該是為了化簡方便才直接把d設成8c
→ skyHuan: https://i.imgur.com/tnmjmaB.jpg
→ skyHuan: 林立宇講義似乎有帶到要有d那項的原因
推 rockieloser: 53題可以詳細一點嗎 想問@@
→ ENGneweu: 謝謝sky大QQ
→ ENGneweu: 53部分 我是這樣寫出遞迴
→ ENGneweu: https://i.imgur.com/ssY9nqN.jpg 剩下就是解遞迴
→ rockieloser: 阿 原來是我自己加減法看錯