[理工] 資結 時間複雜度比大小

看板Grad-ProbAsk作者 (mm)時間12年前 (2012/04/23 02:40), 編輯推噓0(0推 0噓 5→)
留言5則, 3人參與, 最新討論串1/3 (看更多)
Q: 請以函數的 order 有小而大排列 (1/2)^n ; (logn)^2 ; n/logn ; 2^n ; n 答案給 : (1/2)^n < (logn)^2 < n/logn < n < 2^n 卡在 : (1) 為什麼 (1/2)^n 最小? (2) n/logn 複雜度比 n 小? 感謝解答~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.249.55.207
→
04/23 08:20, , 1F
(1/2)^n→0 當 n→∞ 而其他的都 →∞
04/23 08:20, 1F
→
04/23 08:21, , 2F
當n≧3時 log(n)＞1 所以 n/log(n) < 1．n
04/23 08:21, 2F
→
04/23 08:21, , 3F
直觀上來看 n 除以一個一直變大的東西 當然比n小
04/23 08:21, 3F
→
04/23 08:24, , 4F
我比較有疑問 (logn)^2跟n/logn 怎麼比?
04/23 08:24, 4F
→
04/23 17:06, , 5F
(logn)^2 = (logn)^3 / (logn) VS n / logn , trivial.
04/23 17:06, 5F
‣ 更多 yyyyu 的文章
文章代碼(AID): #1Fb52fg5 (Grad-ProbAsk)
‣ 更多 yyyyu 的文章
文章代碼(AID): #1Fb52fg5 (Grad-ProbAsk)