[理工] 時間複雜度 Time Complexity

看板Grad-ProbAsk作者 (路人甲)時間10年前 (2016/01/14 00:16), 10年前編輯推噓4(4推 0噓 14→)
留言18則, 6人參與, 最新討論串1/1
N為問題大小，K為大於1的常數。 請比較以下兩個時間複雜度（Time complexity）的大小： K^log(N) log(N^N) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.255.130.167 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1452701805.A.C87.html
推
01/14 00:29, , 1F
等於?
01/14 00:29, 1F
推
01/14 01:21, , 2F
Logn < nlogn吧
01/14 01:21, 2F
推
01/14 01:38, , 3F
log(N^N)=Nlog(N) < K^log(N)=N^log(K) 應該是這樣吧
01/14 01:38, 3F
→
01/14 01:38, , 4F
又看錯了 qq
01/14 01:38, 4F
→
01/14 01:39, , 5F
一個是nlog(n) 一個是大於N^1的多項式
01/14 01:39, 5F
→
01/14 03:05, , 6F
為什麼 K^log(N) 會等於 N^log(K) ?
01/14 03:05, 6F
→
01/14 03:06, , 7F
知道了 , 兩邊 同取 log , 就剛好是 logK * logN
01/14 03:06, 7F
K^log(N) 取 log 為 log(K^log(N)) = log(N) * log(K) log(N^N) 取 log 為 log(N*log(N)) = log(N) + loglog(N) 那麼 [ log(N) * log(K) ] 一定會大於 [ log(N) + loglog(N) ] 嗎 ? @@" ※ 編輯: OSDBNetwork (111.255.130.167), 01/14/2016 03:17:28
→
01/14 09:22, , 8F
K^log(N) = N^log(K) ， K若取2 N
01/14 09:22, 8F
→
01/14 09:24, , 9F
log(N脕) = N 휠logN ，就比N大了
01/14 09:24, 9F
→
01/14 09:25, , 10F
用手機打的數學符號變亂碼了@@
01/14 09:25, 10F
→
01/14 10:12, , 11F
我想了一下 用log就已經壓縮級距了
01/14 10:12, 11F
→
01/14 10:13, , 12F
多項式時間的全部會被壓縮到O(logn)
01/14 10:13, 12F
→
01/14 10:15, , 13F
不是一定大於 是看最大誰比較大
01/14 10:15, 13F
if log(K) > 1 , then [ log(N) * log(K) ] > [ log(N) + loglog(N) ] . if log(K) <= 1 , then [ log(N) * log(K) ] < [ log(N) + loglog(N) ] . 這樣成立嗎? ※ 編輯: OSDBNetwork (111.255.130.167), 01/14/2016 10:29:44
→
01/14 11:22, , 14F
類似這種感覺 沒壓就是nlogn vs n^O(1)
01/14 11:22, 14F
→
01/15 17:18, , 15F
如果K是1.001的話呢? log(N^N)=NlogN >N^logK 嗎
01/15 17:18, 15F
推
01/15 20:48, , 16F
K是1.00001 那logk就<1阿~
01/15 20:48, 16F
→
01/16 01:30, , 17F
基本都會把N和K看成很大 不然2^10000 就會超級大惹~
01/16 01:30, 17F
→
01/16 01:31, , 18F
不過大家還是看成常數項這樣 不然很難討論
01/16 01:31, 18F
‣ 更多 OSDBNetwork 的文章
文章代碼(AID): #1MbdXjo7 (Grad-ProbAsk)