作者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/m.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