推 wilson50101: 感覺兩個都是true 03/26 20:31
→ wilson50101: 把f(n)帶進去解mt就好了吧 03/26 20:31
→ wilson50101: 兩邊差距差蠻多的 03/26 20:31
推 kyrie77: 和麟的作業題目XD 03/27 01:01
推 kyrie77: 應該第一題True，第二題False 03/27 12:00
推 wilson50101: 樓上可以說為什麼第二題false嗎？ 03/27 18:09
→ wilson50101: 沒feel 03/27 18:09
推 kyrie77: 因為如果要用master theorem還有一個條件是af(n/b)<=cf 03/27 19:40
→ kyrie77: (n), for some c<1,∀n，這樣才能適用case3 03/27 19:40
推 wilson50101: 如果f(n)假設成n平方 a=2 b=2的話不就是 03/27 23:15
→ wilson50101: 1/2n平方<=cn平方 03/27 23:15
→ wilson50101: c就可以取1/2 for all n 03/27 23:15
→ wilson50101: 這樣就可以用case 3了不是嗎？ 03/27 23:15
→ wilson50101: 還是我這做法哪裡有問題？ 03/27 23:15
推 kyrie77: 噢噢，問題應該就是出在這題不能一開始就假設f(n)是n^2 04/08 20:21
→ kyrie77: 之類的函數，因為題目是給你一個集合，而如果要套用mas 04/08 20:21
→ kyrie77: ter theorem的話要for all n都符合下面那個式子，因此可 04/08 20:21
→ kyrie77: 以造出非常人工的函數使得每2次迭代都讓f(n)變成不一樣 04/08 20:21
→ kyrie77: 的函數(比如說n^2和n^4) 04/08 20:21