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