Re: [問題] 計算時間複雜度

看板Prob_Solve作者時間12年前 (2011/11/08 22:29), 編輯推噓3(3推 0噓 9→)
留言12則, 3人參與, 最新討論串4/4 (看更多)
又遇到一題不知怎麼辦 http://ppt.cc/3,ef 小弟的兩種想法 但兩種想法出來的答案不同 希望各位解惑 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.255.1.74
推
11/08 22:54, , 1F
lg(nlgn) = lgn + lglgn
11/08 22:54, 1F
→
11/08 22:54, , 2F
別忘了指數裡若是乘的出來要變加的...
11/08 22:54, 2F
→
11/08 22:54, , 3F
對數
11/08 22:54, 3F
→
11/08 22:58, , 4F
可以請問樓上第一行是怎麼來的..?
11/08 22:58, 4F
→
11/08 23:03, , 5F
另外, n!≦n^n 但 lg(n!)=Θ(nlgn), lg(n^n)=Θ(nlgn)...
11/08 23:03, 5F
推
11/08 23:20, , 6F
我沒掛 O() 喔 所以只是普通的對數運算而已
11/08 23:20, 6F
→
11/08 23:33, , 7F
請問L大　lg(nlgn)　我的算法中沒出現這個　不知從哪來的
11/08 23:33, 7F
→
11/08 23:34, , 8F
請問s大　意思是n!和n^n取完lg 複雜度是相等囉!?
11/08 23:34, 8F
→
11/08 23:36, , 9F
但知道lg(n!)和lg(n^n)是相等　該如何用在這題
11/08 23:36, 9F
推
11/09 03:43, , 10F
我看錯了 XD
11/09 03:43, 10F
→
11/09 10:26, , 11F
@lf963: 我的意思是說 取lg相等不代表他們相等
11/09 10:26, 11F
→
11/09 10:27, , 12F
所以取lg無法得到結論
11/09 10:27, 12F
‣ 更多 lf963 的文章
文章代碼(AID): #1EkJpUN1 (Prob_Solve)
‣ 更多 lf963 的文章
文章代碼(AID): #1EkJpUN1 (Prob_Solve)