作者QaOe (昵称肥宅)
看板Grad-ProbAsk
标题[理工] 资结 时间复杂度的T or F
时间Wed Jul 4 14:47:22 2018
https://i.imgur.com/zU0Kiil.jpg
这题我手边的答案是给T
但是不太懂如果是T的话
那C和n_0要怎麽找
不知道是我抄错还是哪里理解错误
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.10.195.121
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1530686845.A.C40.html
1F：推 alan23273850: 记得这题题干的c跟big O定义里面那个c是两回事 07/04 15:55
2F：→ alan23273850: 你必须先替这题的题干c找到一个常数k，假设是3好了 07/04 15:57
3F：→ alan23273850: 然後再找另一个常数系数A，计算A*log(n)^3和n的微分 07/04 16:00
4F：→ alan23273850: 去观察什麽时候log那边的微分永远比n那边小，那这样 07/04 16:00
5F：→ alan23273850: 门槛值n0就找到了 07/04 16:00
6F：→ alan23273850: 最後你再说 for all k 这个事实都成立即可 07/04 16:01
7F：推 EXPCDR: 是T没错 左边是对数等级而已 07/05 22:42
8F：→ EXPCDR: 我找c跟n0不像楼上那麽专业，都是直接找看起来就有符合定 07/05 22:42
9F：→ EXPCDR: 义的数，下面以d=4为例 07/05 22:42
11F：推 EXPCDR: 想请问为什麽第八题会是F 07/05 22:47
12F：→ EXPCDR: 哦我知道了 因为分母可能变0 07/05 23:32
13F：推 alan23273850: 换我不太懂七跟八差在哪 07/06 02:57
14F：推 EXPCDR: 我觉得我想的方式是错的，等看有没有人知道第八题了 07/06 08:46
15F：推 eggy1018: 8,若k=n双边取log後,左边nlog(logn),右边logn,所以左>右 07/06 15:18
16F：推 EXPCDR: 那条件设k不等於n才对吧，可是他条件是k>0 07/06 22:07
17F：推 eggy1018: 应该是说这题k并没有被指定所以没办法确定，但是k=n时 07/07 00:04
18F：→ eggy1018: 我认为会有上述情形发生 07/07 00:04
19F：→ alan23273850: 所以第八题的 k 是变数就对了 07/07 16:52