作者cormen5566 (怕热非洲土着)
看板Grad-ProbAsk
标题Re: [理工] [演算法]-时间复杂度
时间Fri Nov 13 21:00:09 2009
※ 引述《b76516 (阿聪)》之铭言：
: ※ 引述《cormen5566 (怕热非洲土着)》之铭言：
: ※ 引述《b76516 (阿聪)》之铭言：
: : 请问一下
: : 在洪逸跟洪捷的演算法名校攻略秘笈1-20页
: : 1/logn
: : 2= n 这条式子是用两边取log比较得到等号还是用log的公式而得到的？
: lg 2 lg n
: 因为n = n = 2 (*)
: 1/lg n lgn * (1/lg n)
: => n = 2 = 2
: : √2logn √2/logn （开根号是整个2logn一起开根号,後面则是2/logn开根号）
: : 2 ＝n 这条式子又是怎麽来的
: 同(*)
: √(2/lg n) lg n * √(2/lg n) √(2lg n)
: => n = 2 = 2
: : logn √2logn
: : √2 跟2 这两个的时间复杂度怎麽比大小呢？
: lg n lg 2
: √2 = n = n ---(1)
: √2logn √2/logn
: 2 = n ---(2)
: => (1) ≧ (2)
: : 3 loglogn
: : (logn)!的时间复杂度为什麽夹在n 跟n 之间呢？
: 3
: lg((lg n)!) = lg n* lglg n ≧ lg n = 3 lg n <=除了这里不太懂之外
: ~~~~~~~~~~~~~~~~~~~~~~~~~~ 剩下都懂了 谢谢你
lg(x!) = lg(x * (x-1) * (x-2) *... * 1)
= lg x + lg (x-1) + ... + lg(1) ≦ lg x + lg x + ... + lg x
= O(xlg x)
lg(x!) ≧ lg(x/2) + lg(x/2) + ... + lg(x/2) + 0 + ... + 0
---------------v----------------- -----v-----
x/2个 x/2个
= (x/2)lg(x/2)
= O(xlg x)
将x带入lgn则
lg((lg n)!) = O(lg n * lg(lg n))
希望能帮得上忙:-)
: : 1-22页的范例2
: : (4) 3 ln n
: : f(n)=n g(n)= 8
: : 为什麽f(n)=O(g(n))
: ln n ln 8 3
: g(n) = 8 = n ≦ n = f(n)
: => g(n) = O(f(n))
: : 问题有点多 先谢谢大家的回答
: 算到头有点昏~有错请指出罗!!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.235.131
※ 编辑: cormen5566 来自: 140.113.235.131 (11/13 21:00)