PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 资结 时间复杂度的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 是变量就对了
继续阅读
[理工] 离散 第一章的范例10
AAQ8
[理工]线代子嘉题库3-15
aromaraz
Re: [理工] 离散 Catalan number 括号方法
JKLee
Re: [理工] 线代 反矩阵
JKLee
[理工] 离散 Catalan number 括号方法
Heyso
[理工] 线代row space之basis
EXPCDR
Re: [理工] 线代 反矩阵
Honor1984
[理工] 线代 反矩阵
AAQ8
[理工] 资结5-81 BST 的average case!
Aa841018
[理工] 线代 2-39 范例8
LILUNC
Links
booklink
Contact Us: admin [ a t ] ucptt.com