作者AAQ8 ()
看板Grad-ProbAsk
标题[理工] 演算法 判断时间复杂度
时间Fri Oct 5 19:24:24 2018
https://i.imgur.com/Nj6H2VX.jpg
https://i.imgur.com/G9oe7S9.jpg
这题的(c)小题
不知道我这样判断时间复杂度行不行
麻烦各位
感恩
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 219.70.197.208
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1538738667.A.0D8.html
1F：推 skyHuan: 为什麽kloga>c 10/05 19:30
2F：→ skyHuan: 比不出来常常两边取log是可以的但这题看得出指数比多项 10/05 19:31
3F：→ skyHuan: 式大 10/05 19:31
4F：→ AAQ8: 我的想法是把c看成常数乘常数，klogn是常数乘对数，所以klog 10/05 20:01
5F：→ AAQ8: n会大於c，不知道这样正不正确 10/05 20:01
6F：推 wilson50101: nO多项式 10/05 20:22
7F：→ wilson50101: aO指数 10/05 20:22
8F：→ wilson50101: 等级就不一样了 10/05 20:22
9F：→ wilson50101: 是我我就直接这样判断 10/05 20:22
10F：→ wilson50101: c就算给道1000 10/05 20:23
11F：→ wilson50101: 还是赢不了a给1 10/05 20:23
12F：→ wilson50101: 更正 10/05 20:23
13F：→ wilson50101: n^c 10/05 20:23
14F：→ wilson50101: a^n 10/05 20:23
15F：推 skyHuan: kloga>c那句有问题吧，像楼上说的常数要取多少都可以， 10/05 20:32
16F：→ skyHuan: 但n很大的时候等级比较大的还是会比较大 10/05 20:32
17F：推 nannnnn: 是可以这样取log比，但是取log後要看little oh ，但是你 10/05 23:45
18F：→ nannnnn: 写<=有Big oh的感觉 10/05 23:45
20F：推 skyHuan: 一般像logn^logn跟2^n这种才会去同取log比 10/06 00:07
21F：→ skyHuan: (c)小题同取log比也对，在论等级的时候常数系数都可以直 10/06 00:07
22F：→ skyHuan: 接忽略，但这题一个指数一个多项式，层级就不一样了一般 10/06 00:07
23F：→ skyHuan: 直接判断就好了 10/06 00:07
24F：推 skyHuan: 想问na大为什麽同取log之後是little-o，好像没特别注意过 10/06 00:10
25F：→ skyHuan: 这边的little big要怎麽取 10/06 00:10
27F：→ nannnnn: 1-8的第一个定理 只有在little o的情况下这个定理才会成 10/06 10:07
28F：→ nannnnn: 立 10/06 10:07
29F：→ nannnnn: 如果这个定理改成big oh是不一定会成立的，反例很好找， 10/06 10:09
30F：→ nannnnn: 例如n^2跟n^3 10/06 10:09
31F：→ skyHuan: 懂了，原来同取log後要分得出绝对大小才能决定原来函数， 10/06 10:20
32F：→ skyHuan: 之前没特别注意过这种情况，感谢提醒 10/06 10:20
34F：→ AAQ8: 那这个定理1-3和(c)小题是一样的东西吗，不管bigoh或是littl 10/06 14:37
35F：→ AAQ8: eoh都成立? 10/06 14:37
36F：→ nannnnn: 对啊,一样的，根据定义little oh成立则big oh就成立 10/06 14:46
37F：→ nannnnn: 就是说f(n)=o(g(n))则f(n)=O(g(n)) 10/06 14:48
39F：→ skyHuan: little-o是big-o的子集，是小o一定是大O 10/06 20:00