作者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