[理工] 演算法複雜度

看板Grad-ProbAsk作者 (瘋狂阿笨狗)時間6年前 (2019/03/26 15:45), 編輯推噓7(7推 0噓 12→)
留言19則, 2人參與, 6年前最新討論串2/3 (看更多)
https://i.imgur.com/LuBRwcW.jpg
想問這兩題要怎麼證，我的想法是用 master theorem推第一題，但是卡在 Case3的條件二,他的f(n)是在theta 裡, 我不確定能不能直接固定theta裡c1,c2 來做推導，麻煩大家了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.214.167.167 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1553586316.A.710.html
推
03/26 20:31, 6年前 , 1F
感覺兩個都是true
03/26 20:31, 1F
→
03/26 20:31, 6年前 , 2F
把f(n)帶進去解mt就好了吧
03/26 20:31, 2F
→
03/26 20:31, 6年前 , 3F
兩邊差距差蠻多的
03/26 20:31, 3F
推
03/27 01:01, 6年前 , 4F
和麟的作業題目XD
03/27 01:01, 4F
推
03/27 12:00, 6年前 , 5F
應該第一題True，第二題False
03/27 12:00, 5F
推
03/27 18:09, 6年前 , 6F
樓上可以說為什麼第二題false嗎？
03/27 18:09, 6F
→
03/27 18:09, 6年前 , 7F
沒feel
03/27 18:09, 7F
推
03/27 19:40, 6年前 , 8F
因為如果要用master theorem還有一個條件是af(n/b)<=cf
03/27 19:40, 8F
→
03/27 19:40, 6年前 , 9F
(n), for some c<1,∀n，這樣才能適用case3
03/27 19:40, 9F
推
03/27 23:15, 6年前 , 10F
如果f(n)假設成n平方 a=2 b=2的話不就是
03/27 23:15, 10F
→
03/27 23:15, 6年前 , 11F
1/2n平方<=cn平方
03/27 23:15, 11F
→
03/27 23:15, 6年前 , 12F
c就可以取1/2 for all n
03/27 23:15, 12F
→
03/27 23:15, 6年前 , 13F
這樣就可以用case 3了不是嗎？
03/27 23:15, 13F
→
03/27 23:15, 6年前 , 14F
還是我這做法哪裡有問題？
03/27 23:15, 14F
推
04/08 20:21, 6年前 , 15F
噢噢，問題應該就是出在這題不能一開始就假設f(n)是n^2
04/08 20:21, 15F
→
04/08 20:21, 6年前 , 16F
之類的函數，因為題目是給你一個集合，而如果要套用mas
04/08 20:21, 16F
→
04/08 20:21, 6年前 , 17F
ter theorem的話要for all n都符合下面那個式子，因此可
04/08 20:21, 17F
→
04/08 20:21, 6年前 , 18F
以造出非常人工的函數使得每2次迭代都讓f(n)變成不一樣
04/08 20:21, 18F
→
04/08 20:21, 6年前 , 19F
的函數(比如說n^2和n^4)
04/08 20:21, 19F
‣ 更多 gz9548171 的文章
文章代碼(AID): #1ScTYCSG (Grad-ProbAsk)
‣ 更多 gz9548171 的文章
文章代碼(AID): #1ScTYCSG (Grad-ProbAsk)