[理工] 离散_时间复杂度 fmtshk PTT批踢踢实业坊

[理工] 离散_时间复杂度

楼主: fmtshk (fmtshk) 2019-09-01 15:18:21

https://i.imgur.com/yNqc87H.jpg
https://i.imgur.com/ORQuyyY.jpg
请问黄线处，-log n = O(1)应该怎么解释好呢？
记得是时间复杂度为负的时候就是常数？
但从那个定义，看起来是要开绝对值的意思吗？开完就变正log n ?
观念有点模糊，求高端教一下@@

作者: JKLee (J.K.Lee) 2019-09-01 16:33:00

根据你贴的定义，答案是错的

楼主: fmtshk (fmtshk) 2019-09-01 17:32:00

那么应该改成什么才对呢？

作者: JKLee (J.K.Lee) 2019-09-01 17:34:00

你的想法没有错比较保险的做法是去翻该学校教算法的教科书，查看big-O的定义以及有没有类似习题(负函数的复杂度)的解答

作者: DLHZ ( ) 2019-09-01 22:14:00

O(1)只是比较不靠近但还是符合定义吧？修正我觉得应该是O(logn)才对

作者: frank1688 (frank1688) 2019-09-02 23:13:00

凭印象，记得子嘉好像有说过，那个绝对值有没有是没有差的，只是在数学上为了严谨才加的，实际上在乎的只有成长率所以你看资料结构或算法的可能就不会写

继续阅读

[理工] 算法257！（NP)Aa841018 [理工] OS 同步shinle14 [理工] 离散同构shinle14 [理工] 线代正规算子AdonisLam [理工] 线代伴随算子AdonisLam 线代矩阵ranks42420808 [理工] 线代 7-48ZaneLin [理工]线代_关于四维cubefmtshk [理工] 离散组合5-42 5-54nwww9542 [理工] 线代AdonisLam