[理工] 時間複雜度 Time Complexity

[OSDBNetwork (路人甲)]

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
推 yaxauw: 等於?
推 odanaga: Logn < nlogn吧
推 f1256421: log(N^N)=Nlog(N) <  K^log(N)=N^log(K) 應該是這樣吧
→ odanaga: 又看錯了 qq
→ f1256421: 一個是nlog(n)  一個是大於N^1的多項式
→ OSDBNetwork: 為什麼 K^log(N) 會等於 N^log(K) ?
→ OSDBNetwork: 知道了 , 兩邊 同取 log , 就剛好是 logK * logN
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

→ Denim5566: K^log(N) = N^log(K) ， K若取2    N
→ Denim5566: log(N脕) = N 휠logN ，就比N大了
→ Denim5566: 用手機打的數學符號變亂碼了@@
→ odanaga: 我想了一下 用log就已經壓縮級距了
→ odanaga: 多項式時間的全部會被壓縮到O(logn)
→ odanaga: 不是一定大於 是看最大誰比較大
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
→ odanaga: 類似這種感覺 沒壓就是nlogn vs n^O(1)
→ loucms: 如果K是1.001的話呢? log(N^N)=NlogN >N^logK 嗎
推 Denim5566: K是1.00001 那logk就<1阿~
→ f1256421: 基本都會把N和K看成很大  不然2^10000 就會超級大惹~
→ f1256421: 不過大家還是看成常數項這樣  不然很難討論