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