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

看板Grad-ProbAsk作者 (小阮)時間15年前 (2010/09/19 20:10), 編輯推噓2(2推 0噓 5→)
留言7則, 5人參與, 最新討論串7/9 (看更多)
比較 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
推
09/20 23:53, , 1F
我覺得2^n比較大
09/20 23:53, 1F
→
09/21 18:24, , 2F
比較怪地方第2步再取log log(n*log2) 怎變成logn
09/21 18:24, 2F
→
09/21 18:27, , 3F
很明顯帶3就很清楚 2^3=8 ,3^1.09=3.3 如果log以10為底的話
09/21 18:27, 3F
→
09/21 18:28, , 4F
2^3 > 3^(0.4...) , 2^10 >> (log10)^2=1
09/21 18:28, 4F
→
09/21 18:42, , 5F
回suker 原Po的n*log2 應是看成以2為底=n 再取log->logn
09/21 18:42, 5F
推
09/21 18:57, , 6F
相除取lim 應該是2^n比較大
09/21 18:57, 6F
→
09/22 10:29, , 7F
謝啦~ 所以應該是答案給錯了
09/22 10:29, 7F
‣ 更多 juan19283746 的文章
文章代碼(AID): #1CbVslbp (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 7 之 9 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共9篇)
‣ 更多 juan19283746 的文章
文章代碼(AID): #1CbVslbp (Grad-ProbAsk)