[理工] [資結] 時間複雜度

[juan19283746 (小阮)]

比較 O(2^n) 和 O(n^logn) 的大小



我算的:

取log

=> O(nlog2)    O((logn)^2)

再取log

=> O(logn)     O(2loglogn)

所以 O(2^n) > O(n^logn)

和給的答案相反@@


謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.40.87.81
推 christianSK:我覺得2^n比較大
→ suker:比較怪地方第2步再取log log(n*log2) 怎變成logn
→ suker:很明顯帶3就很清楚 2^3=8 ,3^1.09=3.3 如果log以10為底的話
→ suker:2^3 > 3^(0.4...) , 2^10   >> (log10)^2=1
→ KenJcFar:回suker 原Po的n*log2 應是看成以2為底=n 再取log->logn
推 mqazz1:相除取lim 應該是2^n比較大
→ juan19283746:謝啦~  所以應該是答案給錯了