作者ENGneweu (威猛先生)
看板Grad-ProbAsk
標題[理工] 演算法 時間複雜度 P39 41 43
時間Sun Dec 2 17:14:26 2018
抱歉 小弟資質愚昧 又來打擾各位了
第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://webptt.com/m.aspx?n=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
1F：推 cossetannie: 50 T(n,n)=T(1,1) T(n-1,n)=T(1,2) 後面都以此類推 12/02 17:40
2F：→ cossetannie: 53 n=j-i 所以T(n)=T(n-1)+T(n-1)+T(n-2) 12/02 17:44
3F：→ cossetannie: 然後T(1)=1 答案應該是O(n)嗎? 12/02 17:44
4F：→ ENGneweu: 53懂了謝謝 答案是T(n)=O((1+√2)^n) 12/02 18:01
5F：→ ENGneweu: 用特徵方程式解 12/02 18:02
6F：→ ENGneweu: 50也懂了謝謝 不是很好想 12/02 18:12
7F：推 skyHuan: 50 這是洪逸的作法 12/03 01:46
9F：推 skyHuan: 57的精神就是要假設你的猜測是對的 12/03 02:01
11F：→ skyHuan: 重點應該設T(k)那邊，c(klogk)^2那邊應該還可以理解因為 12/03 02:01
12F：→ skyHuan: 要證在這個等級裡面，dk^2‧logk這項好像不能漏(我把他理 12/03 02:01
13F：→ skyHuan: 我是覺得這個證明有點倒果為因的感覺，一直也覺得怪怪的X 12/03 02:01
14F：→ skyHuan: D，要證P是對的先假設P再推出P正確所以得證(?) 12/03 02:01
15F：推 skyHuan: 上面括號被切掉了... 12/03 02:03
16F：→ skyHuan: d的那項我把他理解成要跟原函數有關係所以這項不能漏， 12/03 02:03
17F：→ skyHuan: 詳解應該是為了化簡方便才直接把d設成8c 12/03 02:03
19F：→ skyHuan: 林立宇講義似乎有帶到要有d那項的原因 12/03 02:08
20F：推 rockieloser: 53題可以詳細一點嗎 想問@@ 12/03 03:42
21F：→ ENGneweu: 謝謝sky大QQ 12/03 07:00
22F：→ ENGneweu: 53部分 我是這樣寫出遞迴 12/03 07:02
24F：→ rockieloser: 阿 原來是我自己加減法看錯 12/03 08:55