作者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/cn.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