作者sdfg014025xx (随便就好)
看板Grad-ProbAsk
标题[理工] DS 时间复杂度 三题
时间Sun Nov 11 23:50:14 2018
洪逸的题库班作业，当时期中考所以今天才写
有些对完答案不太懂想请教各位
1.
https://i.imgur.com/ncK826Z.jpg
这题不太会算
2.
https://i.imgur.com/H8XJ7MY.jpg
上面那题不是应该要是positive constant才会对吗？
下面那题好像是Master theorey case1
但是n^log3(底数2）跟nlogn要怎麽比较呢？
感谢各位
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.195.4.87
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1541951416.A.3E8.html
1F：推 skyHuan: 1用sigma取for回圈的上下界再化简11/12 00:11
2F：→ skyHuan: 2题目是“exist”，如果改成任意constant就错11/12 00:11
3F：推 ponponjerry: 下面那题(b)不能用Master，要用展开代入喔！我刚刚11/12 00:29
4F：→ ponponjerry: 写得很乱，如果有需要我可以重写给你参考11/12 00:29
5F：推 skyHuan: 咦可以master吧 我就是用master做的(?11/12 00:40
6F：推 alen0303: lg3大概是1.XXX 那就只要比较O(n^0.XXX)和O(logn)11/12 00:47
7F：→ ponponjerry: 可以吗？！请问你ε怎麽取什麽11/12 00:47
8F：→ alen0303: 多项式必定比log型大 同取log比较就好了11/12 00:47
9F：推 skyHuan: 取0.0000001多项式还是比log大11/12 00:50
10F：→ ponponjerry: 对喔 我耍笨了QQ11/12 01:03
对齁 我也忘了 感谢各位
※ 编辑: sdfg014025xx (123.195.4.87), 11/12/2018 01:06:23
11F：推 wilson50101: 不好意思想请问一下有答案可以给我吗？ 11/12 17:08
12F：→ wilson50101: 我补tkb可是都没拿到答案@@ 11/12 17:08
13F：→ skyHuan: 下一堂上课会公布喔 11/12 17:44
14F：→ o5739201: 马的tkb更新超慢 今天才出现第二堂 11/12 21:18
15F：嘘 skyHuan: 大硕不EY 11/12 21:41
16F：推 EXPCDR: 不对吧第2上面那题题意是exist每错，是错在要大於等於n0 11/13 00:29
17F：→ EXPCDR: 而不是大於等於1 11/13 00:29
18F：推 skyHuan: 答案是true吧 c找再大一点n>1也会对(? 11/13 01:07
19F：推 EXPCDR: 对欸 话说你们解答哪里来的 第二堂课才会给吗 11/13 11:16
20F：→ EXPCDR: 我以为解答也是用发的 11/13 11:17