[理工] 演算法 判斷時間複雜度

看板Grad-ProbAsk作者時間7年前 (2018/10/05 19:24), 編輯推噓7(7推 0噓 32→)
留言39則, 4人參與, 7年前最新討論串1/1
https://i.imgur.com/Nj6H2VX.jpg
https://i.imgur.com/G9oe7S9.jpg
這題的(c)小題 不知道我這樣判斷時間複雜度行不行 麻煩各位 感恩 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.70.197.208 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1538738667.A.0D8.html
推
10/05 19:30, 7年前 , 1F
為什麼kloga>c
10/05 19:30, 1F
→
10/05 19:31, 7年前 , 2F
比不出來常常兩邊取log是可以的但這題看得出指數比多項
10/05 19:31, 2F
→
10/05 19:31, 7年前 , 3F
式大
10/05 19:31, 3F
→
10/05 20:01, 7年前 , 4F
我的想法是把c看成常數乘常數，klogn是常數乘對數，所以klog
10/05 20:01, 4F
→
10/05 20:01, 7年前 , 5F
n會大於c，不知道這樣正不正確
10/05 20:01, 5F
推
10/05 20:22, 7年前 , 6F
nO多項式
10/05 20:22, 6F
→
10/05 20:22, 7年前 , 7F
aO指數
10/05 20:22, 7F
→
10/05 20:22, 7年前 , 8F
等級就不一樣了
10/05 20:22, 8F
→
10/05 20:22, 7年前 , 9F
是我我就直接這樣判斷
10/05 20:22, 9F
→
10/05 20:23, 7年前 , 10F
c就算給道1000
10/05 20:23, 10F
→
10/05 20:23, 7年前 , 11F
還是贏不了a給1
10/05 20:23, 11F
→
10/05 20:23, 7年前 , 12F
更正
10/05 20:23, 12F
→
10/05 20:23, 7年前 , 13F
n^c
10/05 20:23, 13F
→
10/05 20:23, 7年前 , 14F
a^n
10/05 20:23, 14F
推
10/05 20:32, 7年前 , 15F
kloga>c那句有問題吧，像樓上說的常數要取多少都可以，
10/05 20:32, 15F
→
10/05 20:32, 7年前 , 16F
但n很大的時候等級比較大的還是會比較大
10/05 20:32, 16F
推
10/05 23:45, 7年前 , 17F
是可以這樣取log比，但是取log後要看little oh ，但是你
10/05 23:45, 17F
→
10/05 23:45, 7年前 , 18F
寫<=有Big oh的感覺
10/05 23:45, 18F
→
10/05 23:50, 7年前 , 19F
10/05 23:50, 19F
推
10/06 00:07, 7年前 , 20F
一般像logn^logn跟2^n這種才會去同取log比
10/06 00:07, 20F
→
10/06 00:07, 7年前 , 21F
(c)小題同取log比也對，在論等級的時候常數係數都可以直
10/06 00:07, 21F
→
10/06 00:07, 7年前 , 22F
接忽略，但這題一個指數一個多項式，層級就不一樣了一般
10/06 00:07, 22F
→
10/06 00:07, 7年前 , 23F
直接判斷就好了
10/06 00:07, 23F
推
10/06 00:10, 7年前 , 24F
想問na大為什麼同取log之後是little-o，好像沒特別注意過
10/06 00:10, 24F
→
10/06 00:10, 7年前 , 25F
這邊的little big要怎麼取
10/06 00:10, 25F
→
10/06 10:07, 7年前 , 26F
https://imgur.com/a/w6UF1G1 根據林立宇老師演算法講義
10/06 10:07, 26F
→
10/06 10:07, 7年前 , 27F
1-8的第一個定理 只有在little o的情況下這個定理才會成
10/06 10:07, 27F
→
10/06 10:07, 7年前 , 28F
立
10/06 10:07, 28F
→
10/06 10:09, 7年前 , 29F
如果這個定理改成big oh是不一定會成立的，反例很好找，
10/06 10:09, 29F
→
10/06 10:09, 7年前 , 30F
例如n^2跟n^3
10/06 10:09, 30F
→
10/06 10:20, 7年前 , 31F
懂了，原來同取log後要分得出絕對大小才能決定原來函數，
10/06 10:20, 31F
→
10/06 10:20, 7年前 , 32F
之前沒特別注意過這種情況，感謝提醒
10/06 10:20, 32F
→
10/06 14:35, 7年前 , 33F
10/06 14:35, 33F
→
10/06 14:37, 7年前 , 34F
那這個定理1-3和(c)小題是一樣的東西嗎，不管bigoh或是littl
10/06 14:37, 34F
→
10/06 14:37, 7年前 , 35F
eoh都成立?
10/06 14:37, 35F
→
10/06 14:46, 7年前 , 36F
對啊,一樣的，根據定義little oh成立則big oh就成立
10/06 14:46, 36F
→
10/06 14:48, 7年前 , 37F
就是說f(n)=o(g(n))則f(n)=O(g(n))
10/06 14:48, 37F
推
10/06 19:59, 7年前 , 38F
10/06 19:59, 38F
→
10/06 20:00, 7年前 , 39F
little-o是big-o的子集，是小o一定是大O
10/06 20:00, 39F
‣ 更多 AAQ8 的文章
文章代碼(AID): #1Rjqdh3O (Grad-ProbAsk)