[理工] 演算法 時間複雜度 多題

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