作者cormen5566 (怕热非洲土着)
看板Grad-ProbAsk
标题Re: [理工] [演算法]-时间复杂度
时间Fri Nov 13 19:34:47 2009
※ 引述《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
: 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