[理工] 资结 时间复杂度的T or F

楼主: QaOe (暱称肥宅)   2018-07-04 14:47:22
https://i.imgur.com/zU0Kiil.jpg
这题我手边的答案是给T
但是不太懂如果是T的话
那C和n_0要怎么找
不知道是我抄错还是哪里理解错误
作者: EXPCDR (EXPCDR)   2018-07-06 08:46:00
我觉得我想的方式是错的,等看有没有人知道第八题了
作者: alan23273850   2018-07-06 02:57:00
换我不太懂七跟八差在哪
作者: EXPCDR (EXPCDR)   2018-07-05 22:42:00
是T没错 左边是对数等级而已我找c跟n0不像楼上那么专业,都是直接找看起来就有符合定义的数,下面以d=4为例https://i.imgur.com/MgjoYZg.jpg想请问为什么第八题会是F哦我知道了 因为分母可能变0
作者: alan23273850   2018-07-04 15:55:00
记得这题题干的c跟big O定义里面那个c是两回事你必须先替这题的题干c找到一个常数k,假设是3好了然后再找另一个常数系数A,计算A*log(n)^3和n的微分去观察什么时候log那边的微分永远比n那边小,那这样门槛值n0就找到了最后你再说 for all k 这个事实都成立即可
作者: eggy1018 (羅密歐與豬過夜)   2018-07-06 15:18:00
8,若k=n双边取log后,左边nlog(logn),右边logn,所以左>右
作者: EXPCDR (EXPCDR)   2018-07-06 22:07:00
那条件设k不等于n才对吧,可是他条件是k>0
作者: eggy1018 (羅密歐與豬過夜)   2018-07-07 00:04:00
应该是说这题k并没有被指定所以没办法确定,但是k=n时我认为会有上述情形发生
作者: alan23273850   2018-07-07 16:52:00
所以第八题的 k 是变量就对了

Links booklink

Contact Us: admin [ a t ] ucptt.com