[理工] 算法判断时间复杂度 AAQ8 PTT批踢踢实业坊

楼主: AAQ8 (不要就是要) 2018-10-05 19:24:24

https://i.imgur.com/Nj6H2VX.jpg
https://i.imgur.com/G9oe7S9.jpg
这题的(c)小题
不知道我这样判断时间复杂度行不行
麻烦各位
感恩

作者: skyHuan (Huan) 2018-10-06 19:59:00

https://imgur.com/YepKQaE.jpglittle-o是big-o的子集，是小o一定是大O

作者: skyHuan (Huan) 2018-10-06 10:20:00

懂了，原来同取log后要分得出绝对大小才能决定原来函数，之前没特别注意过这种情况，感谢提醒

楼主: AAQ8 (不要就是要) 2018-10-06 14:35:00

https://i.imgur.com/vrcZmRt.jpg那这个定理1-3和(c)小题是一样的东西吗，不管bigoh或是littleoh都成立?

作者: nannnnn (nannnnn) 2018-10-06 14:46:00

对啊,一样的，根据定义little oh成立则big oh就成立就是说f(n)=o(g(n))则f(n)=O(g(n))

作者: nannnnn (nannnnn) 2018-10-06 10:07:00

https://imgur.com/a/w6UF1G1 根据林立宇老师算法讲义1-8的第一个定理只有在little o的情况下这个定理才会成立如果这个定理改成big oh是不一定会成立的，反例很好找，例如n^2跟n^3

作者: skyHuan (Huan) 2018-10-05 19:30:00

为什么kloga>c比不出来常常两边取log是可以的但这题看得出指数比多项式大

楼主: AAQ8 (不要就是要) 2018-10-05 20:01:00

我的想法是把c看成常数乘常数，klogn是常数乘对数，所以klogn会大于c，不知道这样正不正确

作者: wilson50101 (我觉得我还不错啊) 2018-10-05 20:22:00

nO多项式aO指数等级就不一样了是我我就直接这样判断c就算给道1000还是赢不了a给1更正n^ca^n

作者: skyHuan (Huan) 2018-10-05 20:32:00

kloga>c那句有问题吧，像楼上说的常数要取多少都可以，但n很大的时候等级比较大的还是会比较大

作者: nannnnn (nannnnn) 2018-10-05 23:45:00

是可以这样取log比，但是取log后要看little oh ，但是你写<=有Big oh的感觉https://imgur.com/a/LxNwjIB

作者: skyHuan (Huan) 2018-10-06 00:07:00

一般像logn^logn跟2^n这种才会去同取log比(c)小题同取log比也对，在论等级的时候常数系数都可以直接忽略，但这题一个指数一个多项式，层级就不一样了一般直接判断就好了想问na大为什么同取log之后是little-o，好像没特别注意过这边的little big要怎么取

继续阅读