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