抱歉 小弟資質愚昧 又來打擾各位了
第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
謝謝各位(_)

50 T(n,n)=T(1,1) T(n-1,n)=T(1,2) 後面都以此類推53 n=j-i 所以T(n)=T(n-1)+T(n-1)+T(n-2)然後T(1)=1 答案應該是O(n)嗎?

53懂了謝謝 答案是T(n)=O((1+√2)^n)用特徵方程式解50也懂了謝謝 不是很好想

50 這是洪逸的作法https://i.imgur.com/6FE4ZVT.jpg57的精神就是要假設你的猜測是對的https://i.imgur.com/sucHoF6.jpg重點應該設T(k)那邊，c(klogk)^2那邊應該還可以理解因為要證在這個等級裡面，dk^2‧logk這項好像不能漏(我把他理我是覺得這個證明有點倒果為因的感覺，一直也覺得怪怪的XD，要證P是對的先假設P再推出P正確所以得證(?)上面括號被切掉了...d的那項我把他理解成要跟原函數有關係所以這項不能漏，詳解應該是為了化簡方便才直接把d設成8chttps://i.imgur.com/tnmjmaB.jpg林立宇講義似乎有帶到要有d那項的原因

53題可以詳細一點嗎 想問@@

謝謝sky大QQ53部分 我是這樣寫出遞迴https://i.imgur.com/ssY9nqN.jpg 剩下就是解遞迴

阿 原來是我自己加減法看錯